[BOJ] 1463 : 1로 만들기

Drakk·2021년 8월 1일

C DP boj 다이나믹 프로그래밍 백준 알고리즘

알고리즘 문제풀이

목록 보기

17/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력

첫째 줄에 1보다 크거나 같고, 10의 6승보다 작거나 같은 정수 N이 주어진다.

🧺출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

🔋예제 입출력

🔮예제 입력1
2

🔮예제 출력1
1

🔮예제 입력2
10

🔮예제 출력2
3

💉문제 분석

🔋분류

다이나믹 프로그래밍(DP)

🔋난이도

실버III

💉문제 풀이

🔋해법

우선 2부터 N까지 반복문을 돌렸습니다.
1번째인덱스의 값은 0이여야 하기때문이죠.

그리고 아래조건을 성립해야합니다.

우선 i번째 인덱스의 값은 i - 1번째인덱스의 값보다 1이 커야합니다.

2로 나눠지는 수는 즉시 i번째값과 값을 비교하여 더 작은것이 채택됩니다.

3으로 나눠지는 수는 즉시 i번째값과 값을 비교하여 더 작은것이 채택됩니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 10e6 + 1;

int adj[MAX];

void dp(int N) {
	for (int i = 2; i <= N; ++i) {
		adj[i] = adj[i - 1] + 1;
		if (i % 3 == 0) adj[i] = std::min(adj[i], adj[i / 3] + 1);
		if (i % 2 == 0) adj[i] = std::min(adj[i], adj[i / 2] + 1);
	}
}

int main() {
	int N;
	std::cin >> N;

	dp(N);
	std::cout << adj[N];
}