-
[백준/BOJ] 1463번 1로 만들기 (C++)알고리즘 문제풀이/백준 2020. 12. 18. 00:57
BFS 혹은 DP로 해결할 수 있는 문제입니다.
DP 풀이는 Bottom-Up 방식으로 1부터 n까지 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우중 최소값을 dp 테이블에 기록하고, 마지막에 dp[n]의 값을 리턴하면 됩니다.
#include <iostream> using namespace std; int dp[1000001]; // i를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값 int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i = 2; i <= n; i++) { // 1을 빼는 경우 dp[i] = dp[i - 1] + 1; // 2로 나누는 경우 if(i % 2 == 0) { dp[i] = min(dp[i], dp[i / 2] + 1); } // 3으로 나누는 경우 if(i % 3 == 0) { dp[i] = min(dp[i], dp[i / 3] + 1); } } cout<<dp[n]; }
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준/BOJ] 11726번 2×n 타일링 (C++) (0) 2020.12.18 [백준/BOJ] 17521번 Byte Coin (C++) (2) 2020.12.18 [백준/BOJ] 18111번 마인크래프트 (C++) (0) 2020.12.17 [백준/BOJ] 14226번 이모티콘 (C++) (2) 2020.12.15 [백준/BOJ] 1525번 퍼즐 (C++) (2) 2020.12.13