들어가는 말
조건 1, 2, 3이 주어질 때 정수 x를 가지고 얼마나 적은 조건으로 1을 만들 수 있는 지에 관한 문제다. 조건 1은 'x가 3으로 나눠 떨어지면 3으로 나눈다', '조건 2는 x가 2로 나눠 떨어지면 2로 나눈다', '조건 3은 1을 뺀다'이다.
다이나믹 프로그래밍으로 푸는 문제다. 다이나믹 프로그래밍이란 문제를 작은 부분으로 나누서 구한 해를 기억해놨다가 필요한 경우 사용하는 문제 풀이 방식을 의미한다. 이 문제는 for을 이용해 bottom-up 방식을 이용했다. Bottom-up방식은 문제를 작은 부분으로 나눠서 그 부분부터 차근차근 풀어가는 방식을 의미한다(재귀함수를 쓸 경우는 top-down 방식이다).
현재 다이나믹 프로그래밍에 워낙 약하기에 어떤 문제 풀이의 큰 틀은 알고 있어도 세세하게 문제를 풀지는 못했다. 그래서 다른 사람의 풀이를 참고했고 다이나믹 프로그래밍에 관해 조금은 알게 되었다.
코드 설명
일단 정수 x를 받는다. 그리고 실행 횟수를 저장할 벡터 v를 사이즈 x+1(0은 쓰지 않을 것이기에)만큼 선언한다. 이때 v의 값은 인덱스 i를 구할 때의 최솟값이다.
v[1]에는 0을 선언한다.
for문을 2부터(1에는 0을 넣어줬다) x까지 돌려주는데, 여기서 주의깊게 봐야 할 점은 i를 x로 만드는 것이다. 문제는 x를 i(1)로 만들 때로 나와있지만, 실질적으로 문제를 풀 때는 i부터 시작해서 x로 올라가야 한다.
먼저 조건 3을 구해준다. 조건 3은 i에다가 1을 빼주는 것이기에 'v[i] = v[i-1] +1'을 해주면 된다. v[i-1]에서 1을 더해주는 이유는 조건이 1을 빼주는 것이었기에 1을 더해준 값에 다가 횟수를 추가하는 것이다.
다음은 조건 2다. 아까 구해줬던 값과 비교를 해주면 된다. 이때 i를 2로 나눈 값에다가 1을 더해줘야 한다. 그 이유는 현재의 i는 i/2 곱하기 2이기 때문이다.
조건 3은 조건 2와 동일하다.
이렇게 모든 값을 구했다면 v[x]를 출력해주면 된다. v[x]에는 1에서부터 x를 만들 때까지의 최소 횟수가 들어가 있다.
코드 설명
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*다이나믹 프로그래밍(문제를 작게 나눠서 과거에 구한 해를 이용한다)
for문을 이용해서 bottom-up방식을 사용한다.
가장 작은 문제들부터 답을 구해가면서 답을 찾는 방식이다.*/
int main() {
int x = 0;
cin >> x;
/*실행 횟수를 넣을 벡터
벡터의 인덱스 값이 i번째 숫자를 구하는데 최소의 실행 횟수이다.*/
vector<int> v(x+1);
v[1] = 0;
/*x에서 값을 나눠서 구하는 게 아니라 i부터 시작해서 얼마나 적은 횟수로 x를 만들 수 있느냐를 구하면 된다.
하나의 실행만을 해주는 게 아니라 가능한 모든 실행을 해서 제일 작은 값을 넣어주면 된다.*/
for (int i = 2; i <= x; i++) {
/*조건 3.
* x가 2일 경우.
* 조건 3에 의해 -1을 해주면 바로 1의 값이 나온다. 한 번의 실행을 해줬기 때문에 v[2] = 1이 된다.
* 그렇기에 1의 실행 값에다가 1을 더해서 v[2]의 실행값을 찾으면 된다. */
v[i] = v[i - 1] + 1;
/*조건 2.
* x가 4일 경우.
* 4, 4/2=2. 2-1=1.
* 이렇게 두 개가 최적이다.
* 조건 3을 돌렸을 때는 v[2] = v[1]+1, v[2] = 1이다.
* i가 2로 나눠떨어지니 v[2] = min(v[i], v[i/2]+1)로 v[2]는 값이 1이 유지된다.
* i가 3일 때는 조건 3에 의해 v[3] = v[2] + 1, v[3] = 2. 조건 1에 의해 min(v[3], v[3/3]+1), v[3] = 2.
* i가 4일 대는 조건 3에 의해 v[4] = v[3] + 1, v[4] = 3. 조건 2에 의해 min(v[4], v[4/2]+1), v[4] = 2.
* v[i/2]의 값을 찾는 이유는 x가 2로 나눠떨어지면 2로 나눈다고 했기에 2로 나눴던 값(i)의 횟수를 찾아서 더해주는 것이다.
* 현재의 i는 i/2에서 2를 곱한 값이다.
* 여기서 핵심은 i를 x로 만들 때까지 몇 번의 실행결과가 걸리냐로 돌리는 거다.*/
if (i % 2 == 0) {
v[i] = min(v[i], v[i / 2] + 1);
}
/*조건 1.
조건 2와 동일하다.*/
if (i % 3 == 0) {
v[i] = min(v[i], v[i / 3] + 1);
}
}
/*x라는 값을 구하기까지의 최소의 실행 횟수를 출력해준다.*/
cout << v[x] << '\n';
return 0;
}