1463 1로 만들기
알바끝나고 스트릭 채우려고 쉬운 문제 고르다가 찾은 문제. 왜 이게 실버3일지에 대해서 고민하지 않고 문제 자체가 쉽게 느껴져서 풀었다. 그러나 아무리 식을 써도 답이 안 나와서 구글링한 결과 dp문제였다. 어쩐지 이런 문제가 직관적으로 풀리면 실버3일리가 없지￣へ￣
dp...너무 옛날에 공부한거라 생각이 안 났다. 모든 경우의 수를 담을 배열 만들어서 점화식 이용해서 그 배열을 채우는거라는 딱 그정도의 지식만 있었다. 공부할 때도 점화식을 모르면 문제를 못 푸니까 어렵다고 생각했다. 구글링으로 점화식 컨닝하지 않았다면 못 풀었을 것 같다.
n이 1부터 10일 때까지의 답을 표로 만들었다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 2 | 3 | 3 | 2 | 3 |
표를 분석해보면
- 1은 0이다.
- 나누어 떨어지지 않는 수(5,7)는 f(n-1)+1 로 답이 도출된다. 나누어 떨어질 때까지 빼야 하므로 이전 것 + -- 연산인 1을 더한 값임.
- 2의 제곱수(2,4,8)만 볼 때 f(n/2)+1 로 답이 도출된다.
- 3의 제곱수(3,9)만 볼 때 f(n/3)+1로 답이 도출된다.
- 2와 3의 공배수(6)는 f(n/2)+1과 f(n/3)+1 중 더 작은 수에 접근하면 답이 도출된다
- 10의 경우 2의 배수로 계산하면 (10-5-4-2-1)로 4지만 1을 빼고 9의 배수로 계산하면 (10-9-3-1)로 3이다.
나는 10으로 나눌 때 3의 배수로 계산하면 더 빠르다는 것을 알지만 컴퓨터는 이것을 알 길이 없다. 그러므로 매번 연산때마다 f(n-1)+1과 f(n/2)+1 중 뭐가 더 작은지 비교해서 더 작은 값을 배열에 넣어야 한다. 모든 식마다 경우의 수를 비교해야 한다. 표 분석대로 식을 작성하면 다음과 같다.
점화식대로 식 만들다가 문득 생각난건데 배열을 백만 이상의 큰 단위로 만들면 프로그램이 멈춰버린다. 코드 자체에는 아무런 이상이 없는데 왜그럴까? 백터랑 배열의 차이점은 공간을 연속적으로 사용하느냐의 차이밖에 없는데 하나는 되고 하나는 안된다면 메모리의 문제인걸까?
그리고 min/max 함수는 algorithm 헤더 추가 안 해도 쓸 수 있는거였다...! ㄷㄷ;;
#include <iostream>
#include <vector>
using namespace std;
vector<int> dp(1000001, 0);
int main()
{
int n;
cin >> n;
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for (int i = 4; i <= n; i++)
{
if (i % 2 != 0 && i % 3 != 0)
dp[i] = dp[i - 1] + 1;
else if (i % 2 == 0 && i % 3 == 0)
dp[i] = min(dp[i / 2] + 1, dp[i / 3] + 1);
else if (i % 2 == 0)
dp[i] = min(dp[i / 2] + 1, dp[i - 1] + 1);
else if (i % 3 == 0)
dp[i] = min(dp[i / 3] + 1, dp[i - 1] + 1);
}
cout << dp[n] << endl;
return 0;
}풀고 바로 자려고 했는데 하필 고른게 dp라 정리하는데 오래 걸렸다.
