문제
https://www.acmicpc.net/problem/18122
풀이
일반적인 하노이탑에서 변형을 거친 하노이탑이다. 처음에는 하나씩 DP를 하면 될텐데 자꾸 틀리길래 어떻게 DP를 한 것일까 생각을 했다.
처음에는 i-1 3번째 -> 빨간색 가운데 -> i-1 가운데 -> 검정색 3번째 -> i-1 첫번째 -> 빨간색 3번째 -> i-1 3번째
로 하면 되지 않을까 해서 했는데 안됬다. 그래서 다시보니
i-1 3번째 -> 빨간색 가운데 -> 검정색 가운데 -> i-1 첫번째 -> 검정색 3번째 -> 빨간색 3번째 -> i-1 3번째
로 하면 i-1을 적게쓰는 것을 알고 이걸로 했는데도 안됐고 둘의 min값을 적용했는데도 안됐다.
그래서 왜 안되나 생각을 해봤는데 생각해보니 i-1을 여러번 옮길때 마지막에만 색깔순서에 맞게 해주면 되는 것이었다 그래서 만약 색깔을 고려하지 않고 옮긴다면
i-1 가운데 -> 빨간색 3번째 -> 검정색 3번째 -> i-1 3번째
로 i-1을 두번만 사용하고 옮길 수 있다. 하지만 이렇게 하면 문제에서 원하는 답은 아닌데, 만약 i보다 높은 것을 할때는 이렇게 짝수번을 시행하면 원래대로 된다. 따라서 새로운 second를 만들어서 dp를 아래와 같이 만들어 줬다.
first가 문제 조건대로 맞추는 것이고 second가 색깔을 역순으로 맞추는 것이다. (시간 : 16ms)
그렇게 해서 이 문제는 맞았는데... 코드 길이를 줄여보는 미션을 받아서 이를 수행해 보았다. 일단 먼저 굳이 min을 사용해야 할까생각이 들어 first를 사용하는 것을 빼봤더니 맞았다.(항상 second만 사용하는 것이 최적) (시간 : 16ms)
그다음에는 들여쓰기를 최저한의 수준으로 없애고 했는데도 코드 길이가 줄어들지 않았다. 그래서 first와 second를 사용하지 않을 수 있을까 생각이 들어 빼봤다. 식을 잘 조작하니 되었다. (시간 : 12ms)
이래도 코드 길이가 길다고 하길래 dp를 하나만 사용하면 배열을 사용할 필요가 없지 않나 싶어서 res로 치환해서 아래와 같이 바꿨다. long long int를 빼려는 시도는 처음부터 했던거 같은데 이때쯤부터 빠져도 안틀리더라. 왠지는 모르겠다. (시간 : 4ms) 곱셉을 하나 할꺼면 덧셈이 더 빠르지 않을까해서 사용했는데 차이는 없었다.
이렇게 해서 코드 길이는 짧아졌는데 시간이 0인 사람들이 있길래 대체 어떻게 한건지 싶었는데 생각해보니까 1000000007을 나누는 것을 매 시행 해야할 필요가 있을까 싶었다. log2 (1000000000) = 30 언저리니까 대충 30번마다 한번씩만 시행해줘도 되었다. 그래서 안전빵으로 25마다 시행하는 것으로 바꿨다. (시간 0ms)
이렇게 해보니 세상에 이상한 사람이 참 많다는 것을 느꼈다. 시간에 쫓기는 코테나 대회에서는 이렇게 하지 못하겠지만 나중에 만든 코드를 최적화 할때 적용하면 좋을만한 경험이었다.
근데 이 문제는 아무리 생각해도 플레는 아니다. 예제좀 제대로 주고 골드 3으로 내렸으면 좋겠다. 예제가 너무 구리다.
실수
- 시간이 오래 걸림
- 최적화를 해야하는 문제가 언젠가는 나올 것 같다. 대비하자.
코드
첫 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
vector<pair<long long int, long long int>> dp(1100000, make_pair(0, 0)); // 0 : 색깔 순서 유지하고 움직이기, 1 : 색깔 순서 바꿔서 움직이기
int main() {
int n;
scanf("%d", &n);
dp[1].first = 3;
dp[1].second = 2;
for (int i = 2; i <= n; i++) {
dp[i].first = min(dp[i - 1].second * 4 + 3, dp[i - 1].first + dp[i - 1].second * 2 + 4) % 1000000007;
dp[i].second = (dp[i - 1].second * 2 + 2) % 1000000007;
}
printf("%lld", dp[n].first);
return 0;
}마지막 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long int res;
scanf("%d", &n);
res= 3;
for (int i = 2; i <= n; i++) {
res = (res + res + 5);
if (i % 25 == 0)
res = res % 1000000007;
}
printf("%d", res % 1000000007);
return 0;
}여정
