이번 문제는 백준의 골드 4 문제 여왕벌 문제이다.
문제를 한 번 차근차근 읽어보도록 하자.
가로세로가 최대 700칸인 벌집이 주어진다.
매일 애벌레가 자라는 정도가 주어지며, 최대 1,000,000일까지 주어진다.
0 1 2를 자라는 정도로, 3 종류의 값이 주어진다.
예를 들어 1 2 2는 0, 1, 1, 2, 2가 되는 것이다.
주어진 일 수 만큼 자라는 정도가 주어지게 된다.
이 때 문제의 규칙대로 애벌레가 모두 자랐을 때의 결과를 출력하라.
규칙은 아래와 같다.
가장 왼쪽 열과 가장 위 행이 먼저 자란 뒤, 나머지가 자란다.
나머지는 좌, 상, 좌상 중 가장 큰 성장 값에 따라 자란다.
문제를 어떻게 해결할 수 있을까?
구현
내 생각에는 단순한 구현 문제로 보인다.
하지만 최대 일 수가 1,000,000인 것을 보아하니, 효율성이 문제가 될 것같다.
나는 먼저 아래와 같은 코드로, 단순히 구현해 보았다.
while(day--){
for (int i = 0; i < 3; i++)
cin >> growing_info[i];
// 여기서 0 1 2 각각 입력받기
int curr_idx = 0;
for (int i = row - 1; i >= 0; i--) {
while (growing_info[curr_idx] == 0)
curr_idx++;
growing_map[i][0] = curr_idx;
honeycomb[i][0] += curr_idx;
growing_info[curr_idx]--;
}
for (int i = 1; i < row; i++) {
while (growing_info[curr_idx] == 0)
curr_idx++;
growing_map[0][i] = curr_idx;
honeycomb[0][i] += curr_idx;
growing_info[curr_idx]--;
}
// 여기까지가 꺽쇠 모양으로 키우기 O(2N-1)
for (int i = 1; i < row; i++) {
for (int j = 1; j < row; j++) {
int growth = max(growing_map[i][j-1], max(growing_map[i-1][j], growing_map[i - 1][j - 1]));
// 위, 왼, 대각선에서 가장 큰 값
honeycomb[i][j] += growth; // 그대로 더해주기
growing_map[i][j] = growth; // 성장세도 저장
}
} // 여기가 나머지 키우기 O(N^2) => 시간초과 발생
}당연히 시간초과가 발생했다. 시간복잡도를 계산해보자.
가장 먼저 자라는 애벌레들을 키우는 것은 O(2N-1)밖에 걸리지 않는다.
하지만 문제는 이후 남은 애벌레들을 키우는 것이다.
현재 나는 이중 for문을 사용했으니, O(N^2)이 될 것이다.
이게 만약 일 수가 늘어나 1,000,000일에 대해 진행한다고 가정하면,
1,000,000 * 700 * 700은 약 5억 정도가 되는 값이다.
즉, O(N^2)으로는 이 문제를 절대 해결할 수 없다!
그럼 O(nlogn)으로는 가능할까?
log700은 약 2.845가 되므로, 700 * log700은 약 1992이다.
1,000,000에 곱하게 되면, 약 2억에 달하는 결과가 나온다.
그럼 남은 애벌레를 키우는 경우는 O(N)만에 끝내야 한다는 결론에 다다른다.
남은 애벌레를 한 번에 계산하기
생각해보니 너무 바보같이 로직을 작성했다.
남은 애벌레를 성장시키는 로직은 생각해보면, 마지막에 한 번만 계산하면 된다.
그 이유가 뭘까?
기본적으로 성장세는 증가하기만 하도록 주어진다고 했다.
그럼 자연스럽게 좌, 좌상, 상중에 상이 가장 성장세가 클 것이다.
그럼 모든 날에 대한 성장세를 더한 뒤 마지막에 상의 성장세만 더해주면?
결국은 매번 더한 것과 동일한 결과가 나올 것이다.
아래와 같이 로직을 수정했다.
while(day--){
for (int i = 0; i < 3; i++)
cin >> growing_info[i];
// 여기서 0 1 2 각각 입력받기
int curr_idx = 0;
for (int i = row - 1; i >= 0; i--) {
while (growing_info[curr_idx] == 0)
curr_idx++;
growing_map[i][0] = curr_idx;
honeycomb[i][0] += curr_idx;
growing_info[curr_idx]--;
}
for (int i = 1; i < row; i++) {
while (growing_info[curr_idx] == 0)
curr_idx++;
growing_map[0][i] = curr_idx;
honeycomb[0][i] += curr_idx;
growing_info[curr_idx]--;
}
// 여기까지가 꺽쇠 모양으로 키우기 O(2N-1)
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < row; j++) {
int growth = growing_map[i-1][j];
// 위, 왼, 대각선에서 가장 큰 값
honeycomb[i][j] += growth; // 그대로 더해주기
growing_map[i][j] = growth; // 성장세도 저장
}
} // 여기가 나머지 키우기 O(N^2)하지만 안타깝게도 83점을 받게 되었다.
83점을 받았다는 것은, 마지막 문항인 4번에서 시간 초과가 발생한 것이다.
어디서 시간을 더 줄일 수 있을까?
누적 합
결론부터 말하자면, 누적 합을 이용해 O(N)만에 풀 수 있다.
아무리 고민해도 도저히 생각이 나지 않아, 풀이를 참고하게 됐다.
당연히 배열을 2차원으로 선언해 풀 생각만 했는데, 머리가 띵 했다.
왜 O(N)인 1차원 배열로도 풀 수 있을까?
위에서 내가 언급했던 대로, 상 방향의 성장세만 알고 있으면 되는게 핵심이다.
남은 애벌레들의 상 방향의 성장세만 고른다고 생각을 해보자.
그럼 자연스럽게 아래와 같은 표가 됨을 알 수 있다.
위의 표를 살펴보면, 가장 첫 열을 제외한 가장 첫 행의 값들이 그대로 내려온다.
그렇다. 상 방향의 성장세만 고르면, 어차피 모두 같은 값이 내려가게 된다.
따라서 아래와 같이 코드를 수정할 수 있다.
int zero = 0, one = 0, two = 0;
while(day--){
cin >> zero >> one >> two;
for (int i = zero; i < zero + one; i++)
honeycomb[i]++;
for (int i = zero + one; i < (2 * row - 1); i++)
honeycomb[i] += 2;
}
for (int i = 0; i < row; i++) {
cout << honeycomb[row - i - 1] << " ";
for (int j = 1; j < row; j++) {
cout << honeycomb[row + j - 1] << " ";
}
cout << '\n';
}1차원 배열을 700 * 2 - 1 크기로 선언한다.
즉 성장세를 가장 처음 저장할 꺾쇠 모양의 칸만 남기는 것이다.
이후, 주어지는 성장세에 맞춰 꺾쇠 모양의 칸을 채운다.
마지막으로 출력시에, 가장 첫 열은 따로 출력하도록 한다.
나머지 열들은 모두 각각 같은 값을 같게되니, 그냥 반복 출력하면 된다!
구현 문제를 풀 때 이렇게 효율적인 아이디어를 생각하는 게 어렵다.
좀 더 연습을 통해 사고력을 기르도록 하자.