[백준 알고리즘] 1463번: 1로 만들기
May 05, 2020
1463번: 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.접근 방법:
DP 연습문제. dp 배열 안에 어떤 수 i를 만드는데 걸리는 최소 횟수를 넣어두고 이를 이용해서 계속 누적시킨다. 최소값을 구해야되기 때문에 세가지 조건이 가능한지 모두 테스트 해보고 가능한 조건들끼리 비교해서 횟수를 비교해줘야 하는데, 3번 조건인 1을 뺀다는 모든 수에 대해서 적용할 수 있는 조건이므로 -1을 했을 때 걸리는 횟수를 일단 dp에 넣어두고 1번 조건과 2번조건을 검사해서 해당하는 조건에 걸리는 횟수를 현재 dp에 들어있는 값과 비교하여 더 작은 값으로 업데이트 해준다.
통과 코드:
#include<iostream>
#include<vector>
using namespace std;
vector<long long> dp(102, -1);
long long p (int n){
if (dp[n] != -1) return dp[n];
return dp[n] = p(n-2) + p(n-3);
}
int main (){
int N;
cin >> N;
for (int i = 1 ; i <= 3 ; i++) dp[i] = 1;
while(N--){
int t;
cin >> t;
p(t);
cout << dp[t] << "\n";
}
return 0;
}
