https://www.acmicpc.net/problem/17135



궁수 세 명을 최적의 위치에 배치해서, 가장 많은 적을 죽이도록 하는 문제이다.



따라서 열의 길이를 이용해서, 궁수가 위치할 수 있는 세 곳을 먼저 조합으로 뽑는다.


각각의 궁수에 대해 bfs를 돌린다. 앞에서부터 멀리있는 곳까지 확인할 것이다.


이때 중요한 것이 몇가지 있다.


궁수들은 같은 거리라면 왼쪽에 있는 적부터 공격한다. 따라서 bfs를 수행할 때, 탐색의 순서를 좌, 상, 우 이렇게 해줘야 한다.


또한 궁수들은 동시에 같은 적을 공격할 수 있다고 했기 때문에, 하나의 궁수를 가지고 탐색을 하다가 적을 발견했을 때에, 바로 그 적을 없애면 안 된다.


그걸 없애버리면 동시에 같은 적을 공격할 수 있다는 조건에 위배되기 때문이다.


set에 추가만 해주고, 이번 턴에 죽일 적을 찾았으므로, 바로 현재 궁수의 bfs를 종료해주면 된다.



세 궁수의 탐색이 사정거리만큼 모두 이루어지고 나면 set을 활용해서 지도에서 적을 지우고, set을 비워준다.



시기적절하게 초기화를 해주고, 적들을 지도에서 제거하고, 적들을 이동시키는 잔처리가 중요한 문제였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef pair<int, int> pii;
int m[19][18], tmp[19][18], N, M, d, st = 1, arr[19], dis[19][18];
int dr[3] = { 0,-1,0 }, dc[3] = {-1, 0, 1};
bool isused[18];
queue<pii> q;
set<pii> killed;
 
void bfs(pii start) {
    dis[start.first][start.second]++;
    q.push(start);
    while (!q.empty()) {
        pii cur = q.front(); q.pop();
        if (dis[cur.first][cur.second] >= d) continue; //사정거리 마지막 점
        for (int i = 0; i < 3; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 1 || nc < 1 || nr > N || nc > M || dis[nr][nc] >= 0) continue;
            if (m[nr][nc] == 1) {
                killed.insert({ nr, nc });
                return;
            }
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
        }
    }
}
void init() {
    for(int i = 1 ; i <= N+1 ; i++)
        for(int j = 1 ; j <= M ; j++)
            dis[i][j] = -1;
    while (!q.empty()) q.pop();
}
bool allKilled() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) 
            if (m[i][j] != 0) 
                return false;
        
    return true;
}
int kill() {
    int cnt = 0;
    for (set<pii>::iterator itr = killed.begin(); itr != killed.end(); itr++) {
        m[itr->first][itr->second] = 0;
        cnt++;
    }
    killed.clear();
    return cnt;
}
void move() {
    for (int i = N; i >= 1; i--) 
        for (int j = 1; j <= M; j++) 
            m[i][j] = m[i - 1][j];
}
int ans = 0;
void btk(int k) {
    if (k == 3) {
        
        int killSum = 0;
        while (1) {
            //적 다 사라질 때까지
            if (allKilled()) break;
 
            for (int i = 0; i < 3; i++) {
                bfs({ N + 1, arr[i] });
                init();
            }
            killSum += kill();//죽은 적들 배열에서 제거
        
            move();    
        }
        if (ans < killSum) ans = killSum;
        
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                m[i][j] = tmp[i][j];
        return;
    }
    if (k == 0) st = 1;
    for (int i = st; i <= M; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            btk(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> N >> M >> d;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    btk(0);
    cout << ans;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19
백준 1926번 그림 (C++)  (0) 2019.08.19

https://www.acmicpc.net/problem/17406



배열 돌리기 목록을 꼭 "모두 사용해야 한다"고 했다. 또한 배열을 돌리는 순서에 따라서 결과가 달라지기 때문에, 순열을 사용해서 돌릴 순서를 정해준다.


모든 경우를 다 돌려봐야 하고, 주의할 사항은, 한 순열을 돌린 이후에, 반드시 배열을 원래 상태로 초기화 시켜줘야 한다는 것이다.



배열을 돌릴 때에는, 모든 값을 보존하면서 돌리는 것이 불가능 하다. 돌리는 순서, 방향에 따라서 반드시 모서리중 어느 한 값은 손실이 발생할 수 밖에 없는데, 그 값을 정해서 미리 담아두고, 마지막에 채워주면 된다.


본인은 가장 좌측 상단의 값을 기억해두고, 그 위치를 없어지는 값으로 정했다. 마지막에 그 값이 옮겨가야 할 곳에 넣어주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<limits.h>
struct Spin {
    int r, c, size;
}sp[8];
using namespace std;
 
int R, C, k, m[51][51],tmp[51][51], arr[8];
bool isused[8];
int Min = INT_MAX;
 
void spin(int val) {
    int rr = sp[val].r, cc = sp[val].c, size = sp[val].size;
    for (int l = 1; l <= size; l++) {
        int leftHigh = m[rr - l][cc - l]; //위쪽 변 넣을때 마지막에 넣어주기
        
        for (int row = rr - l; row <= rr + l-1; row++)  //왼쪽 변
            m[row][cc - l] = m[row+1][cc - l];
    
        for (int col = cc - l; col <= cc + l - 1; col++)  //아래쪽 변
            m[rr + l][col] = m[rr + l][col + 1];
        
 
        for (int row = rr + l; row >= rr - l + 1; row--)  //우측 
            m[row][cc + l] = m[row - 1][cc + l];
        
 
        for (int col = cc + l; col >= cc - l + 2; col--)  //상단
            m[rr - l][col] = m[rr - l][col - 1];
        
        m[rr - l][cc - l + 1] = leftHigh; //기억해 놨던 맨 왼쪽 상단 값 넣어줌
    }
    
}
 
void calMin() {
    int inMin = INT_MAX;
    for (int i = 1; i <= R; i++) {
        int Sum = 0;
        for (int j = 1; j <= C; j++) 
            Sum += m[i][j];
        
        if (inMin > Sum) inMin = Sum;
    }
    if (inMin < Min) Min = inMin;
    
}
void init() {
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            m[i][j] = tmp[i][j];
}
void backTracking(int num) {
    if (num == k) {
        for (int i = 0; i < k; i++)
            spin(arr[i]);
        calMin();
        
        init(); //배열 돌리기 이전으로 초기화
        return;
    }
    for (int i = 0; i < k; i++) {
        if (!isused[i]) {
            arr[num] = i;
            isused[i] = true;
            backTracking(num + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> R >> C >> k;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    for (int i = 0; i < k; i++) 
        cin >> sp[i].r >> sp[i].c >> sp[i].size;
    
    backTracking(0);
    cout << Min;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19
백준 1926번 그림 (C++)  (0) 2019.08.19
백준 10254 고속도로 C++  (0) 2019.08.17

https://www.welcomekakao.com/learn/courses/30/lessons/42891



정확성 테스트는, 그냥 조건대로 시뮬레이션을 돌리면 통과할 수 있지만, 효율성 테스트는 통과할 수 없다.


k의 범위가 매우 큰데, 나이브하게 풀면 k번 탐색해야하기 때문이다.



k번 탐색할 게 아니라, 최대로 음식의 개수만큼만 탐색하도록 구현할 수 있다.


음식을 먹는 데 소요되는 시간을 오름차순으로 정렬하고, 


(현 시점에서 가장 적은 시간이 소요되는 음식의 시간 * 남아있는 음식의 수)만큼의 시간을 한 번에 감소시킬 수 있다.


당연히 k도 갱신되어야 하고, 위에 계산한 시간이 k보다 작아야 가능하다.


저 시간이 k보다 크다면, 음식별 소요 시간으로 정렬해 두었던 것을, 다시 본래의 인덱스로 돌려준다. 이것 때문에 초반에 pair에 음식별 소요시간과 그 음식의 번호를 함께 저장하는 것이다.


이제는 나머지 연산을 활용해서, 먹어야할 음식을 찾아주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
int solution(vector<int> ft, long long k) {
    vector<pii> foods;
    for (int i = 0; i < ft.size(); i++) 
        foods.push_back({ ft[i], i + 1 }); //음식의 번호는 1부터
    
    sort(foods.begin(), foods.end());
    int remain = foods.size();
    ll spend, preTime = 0; //spend = 현 시점에서 한번에 지울 수 있는 시간, pretime = 이전에 봤던 음식의 소요 시간
    for (vector<pii>::iterator itr = foods.begin(); itr != foods.end(); itr++, remain--) {
        spend = (itr->first-preTime) * remain;
        preTime = itr->first;
        if (spend == 0) continue;
        else if (spend <= k) { //한번에 spend만큼 지울 수 있으면
            k -= spend;
        }
        else { //한번에 먹을 수 있는 양보다 k가 작으면
            sort(itr, foods.end(), cmp);//다시 음식들 원위치로 정렬
            k %= remain;
            return (itr + k)->second;
        }
    }
    return -1; //먹을 수 있는 게 없어서, spend가 k보다 커진적 없이, 계속 0이라 스킵된 경우
}
int main(void) {
    vector<int> v;
    v = { 3,5,1,6,5,3 };
    int k = 20;
    solution(v, 20);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

카카오 2017 블라인드 테스트 1차: 다트 게임 (C++)  (0) 2019.08.25
2017 카카오 블라인드 테스트 1차: 비밀지도 (C++)  (0) 2019.08.23
카카오 2018 블라인드 테스트: 길 찾기 게임 C++  (0) 2019.08.20
카카오 2018 블라인드 테스트: 실패율 C++  (0) 2019.08.19
카카오 2018 블라인드 테스트: 오픈채팅방 C++  (0) 2019.08.19

문제 풀이 소요 시간을 획기적으로 감소시켜야 할 때 생각해 볼만한 것들



1. 정렬


2. modular 연산


3. 이분탐색



저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 문제 접근 방법' 카테고리의 다른 글

다익스트라 - 함께여행  (0) 2022.11.18
메모리초과  (0) 2019.08.16
런타임 에러 발생 이유 (추가중)  (0) 2019.07.25
배열 최대/최소 기억  (0) 2019.07.09
투포인터 응용  (0) 2019.07.09

https://www.welcomekakao.com/learn/courses/30/lessons/42891



k번 순회하도록 해서 정확도밖에 맞추지 못한 코드이다.


순회 방법을 줄일 아이디어가 필요하다.



처음에 든 생각은, 배열에서 0이 아닌것의 개수와, 배열의 최솟값을 곱하면 이만큼을 한 번에 먹는 것으로 처리할 수 있다는 것.


다른 생각은 정렬해서 k보다 작을동안 묶어서 빼준 이후에, 한 번에 먹을 수 있는 게 k보다 커지면 다시 순회하는 방법이 있을 것 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <string>
#include <vector>
#include<iostream>
typedef long long ll;
using namespace std;
 
int len;
 
 
int solution(vector<int> ft, long long k) {
    bool done = false;
    int answer = 0;
    len = ft.size();
    ll j = 0;
    //findNext(&ft, j);
 
    int cnt = 0, Min = 1000000000;
    for (int i = 0; i < ft.size(); i++) {
        if (ft[i] != 0) cnt++;
        if (ft[i] < Min) Min = ft[i];
    }
 
    for (ll i = 1; i <= k; i++) {
        if (ft[j] != 0) {
            ft[j] -= 1;
        }
        for (int k = 0; k < len; k++) {
            j++;
            if (j == len) j = 0;
            if (ft[j] == 0) {
                if(k == len - 1) done = true; //모든 원소가 0
                continue;
            }
            else
                break;
            
        }
        //for (int k = 0; k < ft.size(); k++) {
        //    cout << ft[k] << ' ';
        //}
        //cout << '\n';
    }
    //cout << "답 : " << j + 1 << '\n';
    //if (done) cout << -1;
    //else
    //     cout << j + 1;
    if (done) return -1;
    else
        return j + 1;
}
int main(void) {
    vector<int> food{ 1,2,2,5 };
    int k = 13;
    solution(food, k);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10
[오답] 백준 1799번: 비숍 (C++)  (0) 2019.07.24
백준 1759번: 암호 만들기 (C++)  (0) 2019.07.23

+ Recent posts

티스토리툴바