백준] 1463 : 1로 만들기

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

1463번: 1로 만들기

 

문제  : 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력  : 

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

 

출력  : 

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

 

 

 

 

 

참고할 개념

 

1) bottom up 방식

[알고리즘] bottom-up 알고리즘 꿀이해

- bottom up방식은 top down 방식과 다르게 재귀를 사용하지 않는 알고리즘으로
재귀가 콜 스택을 쌓을 때 발생하는 memory cost를 절약하는 방식이다.

** 어떠한 유형에서는 top down이 유리할 수도 있으니 두 방식 다 알아두는 것이 좋다.

 

 

2) 연산의 적용

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

위의 문제에서 정수 X가 주어지면, X가 0이나 1일 때는 0이라는 것을 미리 염두해두어야 합니다.

또한 무조건 큰 수로 나누는 게 정답이 아닙니다.

 

만약 X가 2이거나 3이면

이를 1로 만드는 경우의 수는 1입니다.

dp[3을 1로 만드는 최소 횟수] = 1.

dp[2를 1로 만드는 최소 횟수] = 1.

 

 

만약 X가 15라면

1번 방식)

 (1) 15에 1을 뺀다 = 14

 (2) 14를 3으로 나눌 수 없으니 2로 나눈다 = 7

 (3) 7은 2와 3으로 나눌 수 없으니 1을 뺀다.

 (4) 6은 2로 나눈다.

 (5) 3은 3으로 나눈다.

 

2번 방식)

 (1) 15를 3으로 나눈다

 (2) 5는 2와 3으로 나눌 수 없으니 1을 뺀다.

 (3) 4는 2로 나눈다.

 (4) 2는 2로 나눈다.

...

이러한 경우의 수에서 최소 연산 횟수를 구하는 문제입니다.

주어진 정수가 15라면 최소 연산 횟수는 4 겠죠?

 

따라서

dp[X] = dp[X / 3] + 1로

X / 3을 1로 만드는 최소 횟수 + 1번이 됩니다.

 

저도 잘 이해가 안 돼서

반복문으로 출력을 해보았습니다.

주어진 정수가 5일 때,

각 규칙에 대한 출력 결과입니다.

i가 2일 때
X - 1 : dp[2] 는 1
X / 2 : dp[2] 는 1

i가 3일 때
X - 1 : dp[3] 는 2
X / 3 : dp[3] 는 1

i가 4일 때
X - 1 : dp[4] 는 2
X / 2 : dp[4] 는 2

i가 5일 때
X - 1 : dp[5] 는 3

출력 결과를 보시면,
DP의 특징인 '계산된 값 재사용'에 대해 알 수 있습니다.
또한 연산이 될 때마다 값이 갱신되는 것도 알 수 있습니다.

저는 DP 개념과 이러한 문제 유형이 처음이라 제 것으로 만들기에는 시간이 조금 필요할 듯 합니다.

 

 

 

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

// bottom up방식을 이용한다.
// 1을 빼는 계산부터 시작.
// 작은 계산을 통해 미리 배열에 값을 메모이제이션한다.
// 2로 나누거나 3으로 나누는 경우, 최소 값을 배열에 다시 저장.
// 즉, 최소 값이면 값을 갱신한다.

// bottom up 방식을 이용할 땐,
// 배열 초기화를 주어진 크기보다 큰 수로 채워넣는다.

// 1번 규칙일 때, DP[N] = DP[N/3] + 1
// 2번 규칙일 때, DP[N] = DP[N/2] + 1
// 3번 규칙일 때, DP[N] = DP[N-1] +1

int dp[100001];

int main() {

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

	return 0;
}

 

 

 

 

 

 

 

참고한 블로그들

[백준] 1463 - 1로 만들기 (2017-11-07 수정완료)

[백준 1463] 1로 만들기

백준 1463번 : 1로 만들기

[백준 BOJ][DP] 1463 1로 만들기

 

 

 

 

 

... 처음 내 코드

DP가 머에여..? 긁적ㅎ

#include <iostream>
using namespace std;

int main() {
	
	int N;
	int temp = 0;

	cin >> N;
	
	int result[N] = {0,};
	temp = N;
	
	for(int i = 0; i < N; i++){

		for(int j = 0; j < N; j++){
			
			if(temp % 5 == 0){
				temp-=1;
				result[i]++;
			}
			
			if(temp % 3 == 0){
				temp /= 3;
				result[i]++;
				
			}if(temp % 2 == 0){
				temp /= 2;
				result[i]++;
			}
		}
	}
	

	for(int i = 0; i < N; i++){

		cout << result[i] << " ";
	}
	
	return 0;
}