문제 해석 누군가 백트래킹을 시도할 때에는, 조건을 잘못 주면 개망한다고 했다. 내가 그랬다. 이 문제를 풀기 위해서 2일의 시간이 걸렸고, 백준에 40번을 제출했는데 다 틀렸다. 현자타임이 온다. 내가 이것밖에 안되나 싶다. 결국 다른 사람이 작성한 코드를 봤는데도 이해가 잘 안됐다. 허무하다. 구현 #include using namespace std; bool ropes[31][11] = { 0 }; int N, H, M; int answer = 4; bool check() { for (int i = 1; i = answer) return; if (check()) { if (answer > cnt) answer = cnt; return; } if (cnt == 3) return; for (int i ..

문제 해설 나에게 엄청난 좌절을 안겨준 문제이다. 처음 문제를 훑어보았을 때는 1시간이면 풀 수 있을 것이라고 착각했지만, 내 구현 능력이 아직 많이 부족하다는 것을 여실히 보여주었다. 장장 이틀에 걸친 삽질을 통해 풀 수 있었던 문제이다. 앞으로도 열심히 공부해야겠다는 자극을 받았다. 어쨌든, 이 문제는 이해를 바탕으로 구현하는 시뮬레이션 문제이다. 다만, 조건이 조금 까다롭기 때문에 적절한 분기 처리를 해주어야 테스트 케이스를 모두 통과할 수 있다. 나의 경우도 이 조건, 저 조건을 따지다가 시간을 모두 날려먹은 케이스이다. 어쨌든, 내가 풀었던 문제 풀이에 대해서 설명해보겠다. 다음과 같이 3, 2, 2, 1, 1, 1, 1, 2, 2, 3 의 높이를 가진 길과 길이 2의 경사로를 생각해보자. 왼쪽..

1. 문제 2. 접근 방법 중고등학교때 열심히 배웠던 이항계수와 관련된 문제이다. 다음과 같이 n=5, c=2 의 경우를 가정해보자. 계산된 값은 10 이다. 그러므로 문제에서 요구하는 '뒤에서부터 처음으로 0이 아닌 값이 나올 때까지의 0의 개수' 는 1 이다. 이런 식으로, 문제가 요구하는 값을 찾아야 하는데 문제는 범위가 1 ~ 20억이라 자칫하면 시간 초과 오류가 발생할 수 있다. 일반적인 순차 접근은 어림도 없으니, 이제 효율적인 알고리즘을 알아보자. 문제에서 요구하는, 뒤에 0이 발생하는 경우는, 2와 5가 만나야만 가능하다. 2와 5를 곱하면 10이다. 어떤 수에 10이 곱해지면 뒤에 0이 하나 생기는 것이다. 그러므로, 우리는 다음의 알고리즘을 적용하면 답을 구할 수 있다. (1) 분자를 ..

1. 문제 2. 접근 방법 '어떤 수가 가지고 있는 약수를 빠르게 찾는 알고리즘' 을 모르면 해결이 쉽지 않은 문제이다. 나도 이 알고리즘을 몰랐기 때문에, 처음에는 시간 초과를 겪어 당황스러울 수밖에 없었다. 이 문제를 접근하는 방법은 다음과 같다. (1) N개의 숫자를 대상으로, N - 1 만큼 숫자 간의 차이들을 구한다. (2) 이 N - 1개의 '차이'들 중, 가장 작은 값을 찾는다. (3) 위에서 구한 가장 작은 값을 대상으로, 1을 제외한 모든 약수를 구한다. (4) 위에서 구한 모든 약수 중, 전체 숫자를 나눠봤을 때 0으로 나누어 떨어지는 약수들만 출력한다. 예시를 들어보자. 다음과 같이 9, 23, 58 의 3개의 숫자가 있다고 가정해보겠다. 그렇다면 위와 같이, 3개의 숫자들의 차이는 ..

1. 문제 2. 접근 방법 이분 탐색으로 해결할 수 있는 적당한 난이도의 문제... 라고는 하나 접근 방법이 잘 떠오르지 않아 애를 먹었던 문제이다. 이 문제는 브루트 포스적인 방법으로 접근하면, O(N * log N) 이라 시간 초과로 풀 수 없다. 그러므로 효율적인 계산 방법을 생각해야 하는데, 아래와 같이 구할 수 있음을 알게 되었다. 우선, N =5 일 때, 즉 5 X 5 배열을 통해서 계산을 생각해보자. 그리고 여기에서 k = 11 일 때, 즉 B[11] 을 찾는 경우를 생각해보자. 우리가 찾는 11번째의 숫자를 S 이라고 한다면, 다음과 같이 접근해야 한다. "전체 숫자 중에서, S보다 작거나 같은 숫자의 개수가 11개보다 작으면 안된다!" → 만약 그렇다면, 찾는 숫자의 범위를 큰 쪽으로 옮..

1. 문제 2. 접근 방법 이분 탐색의 종류인 Parametric Search 를 이용한 문제이다. 이 문제는 다음과 같은 과정으로 접근해야 한다. (1) 공유기 사이의 최소 거리가 될 수 있는 값은, 1 이다. (2) 공유기 사이의 최대 거리가 될 수 있는 값은, (마지막 공유기의 위치 - 첫 번째 공유기의 위치) 이다. (3) 중간값은 (1)과 (2)에서 구한 값의 중간값이다. (4) 중간값이 가능한 값인지 검사한다. (5) 만약, 중간값이 가능한 값이라면 → 범위를 큰 쪽으로 줄인다. (6) 만약, 중간값이 불가능한 값이라면 → 범위를 작은 쪽으로 줄인다. 여기에서 중간값이 가능한 값인지는 다음과 같이 구할 수 있다. 전체 공유기를 대상으로, 자신의 공유기의 위치에서 이전에 놓았던 공유기의 위치를 ..