/* 블록은 엔개의 타워 형태로 쌓여있습니다. 아이번째 타워에는 단위 크기의 블록이 에이치개 쌓여있습니다. 내부 블록 인접한 블록이 있다고 봅니다. 외부 블록, 한 단위 시간에 외부 블록을 없애다 모든 블록이 없어질 때 까지 걸리는 시간을 구하세요. '자연수 티가 주어지고 티는 25이하 자연수 그리고 케이스의 첫줄에는 타워으 ㅣ개숫 엔이 주어집니다. 두번쨰 ㅜㄹ에는 타워의 블록 개수를 의미하는 자연수가 주어집니다. 문제에 주어진 조건 그대로 이프 왼족 오른쪽 블러수 0일 경우에는 0 현재블럭수보다 많은 경우에는 1 감소 현재 블륵수 보다 적을 경우에는 민 왼쪽, 오른쪽 을 모든 블럭이0 일 될떄까지 반복문을 실행하면 됩니다. 효율적인 알고리즘을 찾아내야 합니다. 같은 답을 가지는 다른 형태의 문제로 알고리즘의 효율성을 높일 수 있습니다. 01810 의 경우 012010의 경우, 주어진 입력값은 다르지만 답은 같습니다. 01210 같이 모든 이웃한 블럭 수 의 차이가 1 이내인 경우, 한번에 블럭을 한 줄 씩 없앨 수 있으므로 모든 블럭 중 최대 값을 차증면 실제로 시뮬레이션을 해보지 ㅇ낳고도 답을 찾을 수 있습니다. 모든 문제를 이웃한 블럭 수의 차이가 1 이내인 형태로 바꾼 후, 그 문제에서 맥스 값을 찾아내면 됩니다. */ #include <iostream> #include <algorithm> using namespace std; long long a[100002], N; int res; void problem_in() { int i; cin >> N; a[0] = 0; for (i = 1; i <= N; i++) cin >> a[i]; a[i] = 0; } void solve() { int i; for (i = 1; i <= N; i++) { if (a[i] > a[i - 1] + 1) a[i] = a[i - 1] + 1; } res = 1; for (i = N; i >= 1; i--) { if (a[i] > a[i + 1] + 1) a[i] = a[i + 1] + 1; if (a[i] > res) res = a[i]; } } int main() { int T, it; cin >> T; for (it = 1; it <= T; it++) { problem_in(); solve(); cout << "Case #" << it << endl << res << endl; } return 0; } |
문제에서 규칙을 찾아서, 하나씩 해결하는 것입니다. 이것을 한번에 할 생각하지 말고, 하나의 포문을 만드는데도 쉽지 않은 것입니다. 문제는 포문2개에 각각 이프문을 포함해서 만든 것이 끊이지만, 규칙을 찾기 위해서는 예제 문제를 몇번이고 곱씹고 말로 풀어낼 필요가 있습니다. 이렇게 해서 문제를 풀어내도록 하겠습니다.