#1463 1로 만들기

# 문제

# 입력 및 출력

# 풀이

규칙을 찾아보려고 했는데 도저히 모르겠더라

그래서 하나하나 적어보고 있는데 다이나믹 프로그래밍 문제 풀었던게 생각나면서 해결이 됐다

변수가 많아져서 좀 복잡하게 쓰긴 했는데 이전 인덱스의 값을 가져와서 최솟값을 차례차례 찾는 방법이긴 하다

#include <iostream>
using namespace std;
int dp[1000001];

int main() {
	dp[1] = 1, dp[2] = 1, dp[3] = 1; // 여기서 문제 발생
	int n;
	cin >> n;
	bool isTwo, isThree;
	for (int i = 4; i <= n; i++) {
		isTwo = false, isThree = false; 
		if (i % 2 == 0) isTwo = true;
		if (i % 3 == 0) isThree = true;
		
		if (isTwo && isThree) dp[i] = min(dp[i - 1], min(dp[i / 2], dp[i / 3])) + 1;
		else if (isTwo) dp[i] = min(dp[i - 1], dp[i / 2]) + 1;
		else if (isThree) dp[i] = min(dp[i - 1], dp[i / 3]) + 1;
		else dp[i] = dp[i - 1] + 1;
	}
	cout << dp[n];
}

처음 짠 코드가 위와 같은데 처음에 틀렸다고 나오더라

그래서 도저히 모르겠어서 또 구글링했다ㅋㅋㅋㅋ

아주 사소한 문제긴 했다

dp[1]=0인데 내가 초기화 할 때 dp[1]=1로 초기화해서 답이 틀렸다고 나온것이었다

위 코드에서 dp[1]=0으로만 해줘도 정답은 된다

 

근데 가시성을 좀 높이기 위해 짧게 바꿔본 코드는 아래와 같다

아래 블로그 참고

https://danidani-de.tistory.com/4

[백준] 1463 1로 만들기 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI

 

#include <iostream>
using namespace std;
int dp[1000001];

int main() {
	dp[1] = 0;
	int n;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
		if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
	}
	cout << dp[n] << endl;
}

어처피 내가 작성한 코드에서도 else문에 들어가기 때문에 dp[i-1]+1 값을 미리 넣어놓고 최솟값을 비교하면 된다

bool 변수만 없어져도 코드가 확 짧아진다ㅋㅋㅋ

 

그리고 min함수는 인자를 2개만 받을 수 있기 때문에 3개의 인자를 쓰려면 안에 min을 한번 더 넣어주기

아래 코드처럼 작성하면 min함수 호출도 2번으로 줄일 수 있음

시간 복잡도 생각해서 간결하게 코드 작성할것!