알고리즘/백준

문제 풀이 구현, 시뮬레이션, 너비 우선 탐색, 그래프 탐색 문제이다. 터질 뿌요들을 탐색할 때, BFS를 이용한다. 상하좌우로 같은 색상의 뿌요들을 탐색했을 때, BFS 탐색의 횟수가 4이상이라면 터질 뿌요들이다. 이 것을 queue explode의 형태로 저장한다. explode 큐를 꺼내면서 뿌요를 터트린다. 터진 뿌요에 해당하는 필드는 '.'으로 값이 변한다. 밑에 빈 공간이 있는 뿌요들은 아래로 떨어져야 한다. 아랫줄부터 검사하면서 현재 검사하는 타일의 값이 '.'일 경우, 해당 타일 바로 위에 있는 뿌요 타일과 값을 바꾼다. 다시 explode 큐를 채우기 위해 BFS로 터질 뿌요들을 탐색하고, explode가 모두 비워질 때까지 반복한다. 코드 #include #include #include..

문제 풀이 구현, 시뮬레이션 문제이다. 파이어볼을 표현할 구조체를 하나 만든다. (fireball) 문제의 방을 vector room[51][51]의 형태로 만들어서 (x, y)의 방의 파이어볼의 데이터를 알 수 있도록 하였다. 각각의 방을 조사하며 파이어볼을 이동시킨다. 이동 시, 속도가 방의 크기보다 클 수 있기 때문에 mod연산을 사용하며 범위를 초과했다면 범위에 맞게 조절해준다. 이동 후의 방에 파이어볼이 합쳐졌다면, (x, y)에서의 vector를 이용해서 합친다. 코드 #include #include using namespace std; typedef struct { int mass; int speed; int direction; }fireball; // 이동 방향 8가지 int dx[8] =..

문제 풀이 누적 합과 이분 탐색을 사용한다. 피자 조각의 최대 개수는 1000개 이므로 O(N * N)으로 해도 시간초과가 발생하지 않는다. A와 B에서 얻을 수 있는 모든 피자 조각을 계산한다. 피자 조각은 끝과 처음이 연결될 수 있으므로 유의해서 더해야 한다. A에서 얻을 수 있는 피자 조각을 기준으로 P와의 차이만큼의 B의 피자 조각의 수를 이분 탐색으로 구한다. 코드 #include #include #include using namespace std; vector A; vector A_parts; vector B; vector B_parts; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int P; int m,..

문제 풀이 이분 탐색을 사용한다. 모두 탑승하는데 소모되는 최소 시간을 이분 탐색한다. 최소 시간은 0, 최대 시간은 (N X 최장 운행 시간)으로 설정했다. mid값을 이용해서 해당 시간 동안 몇 명이 탑승할 수 있는 확인한다. 여기서 주의할 점이 0초 때, 이미 기구에 탑승하고 있기 때문에 현재 탑승한 아이의 수를 미리 N으로 세팅해줘야 한다. 이분 탐색으로 얻은 최소시간은, 마지막 아이가 놀이기구에 탑승한 시점의 시간이다. (최소시간 - 1)분 때, 총 몇 명이 탈 수 있는지 확인한다. (최소시간 % 탑승시간 == 0)이라면 해당 놀이기구에는 최소시간 시점에 탑승할 수 있는 놀이기구이다. 인덱스가 작은 순으로 해당 검사를 하면서 총 탑승한 아이의 수가 N과 같을 때의 인덱스를 출력한다. 코드 #in..

문제 풀이 이분 탐색을 사용한다. 가장 긴 증가하는 부분 수열을 찾는 문제이다. 내가 알던 방법은 O(N * N)으로 전체 계산 수가 16억이 되어 시간 초과가 발생한다. 입력이 들어오면서 검사를 실시한다. 입력값이 현재 수열의 가장 끝에 있는 수를 초과한 경우 바로 수열에 추가된다. 이하일 경우엔 이분 탐색을 실시한다. 현재 수열에서 입력값 이하의 값 중, 최댓값을 입력값으로 교체한다. 이렇게 하면 시간 복잡도가 O(N * logN)으로 줄어든다. 코드 #include #include #include using namespace std; vector nums; // 기존에 입력된 nums에서 num 이하의 값중에서 // 최댓값을 num으로 교체한다. void binary_input(int num) { ..

문제 풀이 이분 탐색을 사용한다. 입력으로 주어지는 수가 상당히 크기 때문에 이분 탐색으로 해결해야 한다. 검사받는 총 시간(mid)을 이분 탐색한다. mid 시간에 심사할 수 있는 사람의 수와 M을 비교하여 범위를 조절한다. mid 시간에 각 심사대에서 심사가능한 사람의 수는 (mid / 소요시간)이다. 코드 #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, M; cin >> N >> M; for (int i = 0; i > temp; nums.push_..

문제 풀이 이분 탐색을 사용한다. 점프할 최소거리(mid)를 이분 탐색한다. 돌 사이의 거리가 mid 미만이라면 돌을 삭제한다. 삭제한 돌의 수와 m을 비교하여 start와 end를 조절한다. 코드 #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int d, n, m; cin >> d >> n >> m; for (int i = 0; i > temp; nums.push_back(temp); } // 시작 지점과 끝 지점을 추가 nums.push_back(0); nums..

문제 풀이 이분 탐색을 사용한다. 용사의 최대 체력을 이분 탐색한다. 최솟값(start)은 1이며 최댓값(end)은 LLONG_MAX - 1로 설정하였다. 용사가 던전 공략에 성공하였다면 답을 갱신하고 end를 줄여서 다시 검사하고, 실패했다면 start를 늘려서 다시 검사한다. 현재 방이 몬스터 방일 경우, 용사는 몬스터를 처치할 때 까지 (몬스터의 체력 / 현재 공격력) 번(turn) 공격을 맞는다. 여기서 (몬스터의 체력 % 현재 공격력 = =0)일 경우 한 번 공격을 덜 맞는다. turn 번 공격을 맞았을 때, 체력이 0이하라면 공략이 실패한 것이며 최대 체력을 늘려서 다시 검사한다. 아이템 방일 경우, 용사의 공격력과 체력을 회복한다. 코드 #include #include #include #in..

문제 풀이 최대 범위에서 최솟값을 찾으므로 이분 탐색을 사용한다. 휴게소를 세울 거리를 이분 탐색하여 찾는다. 휴게소를 세울 수 있는 최소 거리는 중복이 안 되므로 1이다. 최대 거리는 고속도로 마지막에는 세울 수 없으므로 L - 1이다. 휴게소와 휴게소 사이의 거리를 dist라고 할 때, dist 안에서 세울 수 있는 휴게소의 수는 dist / mid이다. 단, dist % mid == 0이라면, 해당 구간의 뒤에 있는 휴게소에 중복으로 세우는 것이므로 1차감한다. 코드 #include #include #include using namespace std; vector nums; vector dists; int main() { ios_base::sync_with_stdio(0); cin.tie(0); c..

문제 풀이 이분 탐색을 사용한다. 모든 수열을 탐색하면 O(n^2)으로 시간초과이다. 각 수열의 수 마다, 다른 수와의 합과 K와의 차이의 최솟값을 찾는다. 최솟값을 찾을 때, 이분 탐색으로 최솟값을 찾고, K와의 차이에 따라 범위를 조절한다. 해당 최솟값이 현재 나온 최솟값과 같다면 answer를 증가하고 더 작다면 갱신한다. 코드 #include #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int t; cin >> t; while (t--) { int n, K; cin >> n >> K; for (int i..