BOJ-1463 1로 만들기

https://www.acmicpc.net/problem/1463

문제 소개

정수 X를 연산 세 개를 적절히 사용하여 1로 만드는 동시에 연산 횟수를 최소화해야 한다.

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

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

Python

문제 풀이

딕셔너리를 사용한 dp로 풀이하였다.

먼저 중간 결과들이 저장될 딕셔너리를 d로 선언하여 입력받은 정수인 N을 키로하는 값을 0으로 초기화한다. 이 딕셔너리에서 키는 현재 정수의 값을, 그리고 값은 해당 키의 값까지 도달하기 위한 연산의 최소 횟수를 의미한다.

결과값을 의미하는 result 는 N으로 초기화한다.

while문은 딕셔너리 d가 비어있게 될 때까지 반복하여 실행한다. while문 내부의 동작을 살펴보면 다음과 같다.

• d의 키값 중 맨 앞의 원소를 X로 선언
  • X가 1이라면 현재 result의 값과 d[X]중 작은 값을 result로 업데이트한 후 d[X]를 삭제하고 result보다 큰 value를 가지는 원소들을 제거
• 3으로 나누기, 2로 나누기, 1 빼기 중 X로 가능한 연산을 모두 진행하여 d의 각 키에 해당하는 최소값 업데이트
• 반복문의 마지막에는 d[X] 제거

큐와 비슷한 방식으로, 딕셔너리에 추가된 순서대로 최종 목적값인 1에 다가가며 최소 횟수를 구하게 된다. BFS와 유사한 방식이라고 생각할 수 있다.

코드

from sys import stdin
input = stdin.readline

N = int(input())
d = {N: 0}
result = N

while len(d) != 0:
    # print(d) # 매 반복마다 d를 확인 가능
    X = list(d.keys())[0]
    if X == 1:
        result = min(d[X], result)
        del d[X]
        # value가 result보다 작은 경우만 남기기
        d = {key: value for key, value in d.items() if value < result}
        continue
    else:
        if X % 3 == 0:
            if X // 3 not in d:
                d[X // 3] = d[X] + 1
            else:
                d[X // 3] = min(d[X] + 1, d[X // 3])
        if X % 2 == 0:
            if X // 2 not in d:
                d[X // 2] = d[X] + 1
            else:
                d[X // 2] = min(d[X] + 1, d[X // 2])
        if X - 1 not in d:
            d[X - 1] = d[X] + 1
        else:
            d[X - 1] = min(d[X] + 1, d[X - 1])
    del d[X]
print(result)

C++

문제 풀이

dp로 풀이한 점은 같지만, 1에서부터 값을 증가시켜가며 n에 도달할 때까지의 연산의 최소 횟수를 구하는 방식으로 풀이하였다.

vector<int> dp의 i번째 인덱스, 즉 dp[i]는 1에서 i까지 도달하기 위한 최소 연산 횟수를 의미한다.

반복문은 2 부터 n까지의 수에 도달하기 위한 최소 연산 횟수를 구하게 된다.

3가지 연산 중 하나를 사용해서 dp[i]에 도달했을 때 연산 횟수 중 가장 작은 값을 dp[현재 수]에 할당하게 된다.

마지막으로 dp[n]을 정답으로 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> dp(n + 1);

	for (int i = 2; i <= n; i++) {
        // i까지 도달하기 위한 최소의 연산 횟수 찾기
		dp[i] = dp[i - 1] + 1;
        // 3으로 나누어지는 경우
		if (i % 3 == 0) {
			dp[i] = dp[i / 3] + 1 < dp[i] ? dp[i / 3] + 1 : dp[i];
		}
        // 2로 나누어지는 경우
		if (i % 2 == 0) {
			dp[i] = dp[i / 2] + 1 < dp[i] ? dp[i / 2] + 1 : dp[i];
		}
	}
	cout << dp[n] << "\n";
    
	return 0;
}