백준 문제/LG전자 준비

⭐1463: 1로 만들기

goldpig 2024. 4. 6. 00:27
728x90

Dynamic Programming(동적계획법)

이 문제를 풀기 위해서는 '동적 계획법' 개념에 대해서 알고 있어야한다. DP는 큰 문제를 작은 문제로 나누어 푸는 알고리즘 기법이다. DP는 다음의 조건을 만족할 때 사용 가능하다.

  • 큰 문제를 작은 문제로 나눌 수 있다.
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

따라서 동적 계획법은 작은 문제의 결과를 메모리에 저장해 두었다가, 같은 작은 문제가 나타날 때마다 이를 활용하여 문제를 풀 수 있다. 그렇기 때문에 메모리 공간을 효율적으로 사용하여 시간복잡도를 줄일 수 있다. 

  • O(N^2) -> O(f(n))으로 다항식 수준으로 개선! 하지만 문제에 따라 다름. 일반적으로는 작은 문제의 정답을 저장해 두고 이를 활용하는 것이기 때문에 작은 문제의 수와 작은 문제를 푸는 시간의 곱이 된다. 따라서, 동적 계획법의 시간 목잡도는 다음과 같다. O(nk). 
    • n: 문제의 크기
    • k: 작은 문제 수

동적 계획법의 구현 방법은 다음의 과정을 반복한다.

  1. 큰 문제를 작은 문제로 나눈다.
  2. 작은 문제를 풀어 정답을 구한다.
  3. 작은 문제의 정답을 저장한다.
  4. 큰 문제를 작은 문제로 나누어 1 ~ 3을 반복한다.

설명

위 와같이 연사 3가지를 활용해서 1을 만드는데 최소 연산 횟수를 구하는 것! 

핵심 아이디어

  • 상향식(bottom-up)으로 풀 수 있다.

예를들어, x=10인 경우, 1을 빼는 연산과 2 or 3으로 나누는 연산 중에 1을 더 빨리 만들기 위해서는 2 or 3의 배수를 먼저 만드는 것이 중요. 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되는데 9의 경우는 9 -> 3 -> 1과정을 거치며 3의 경우는 3-> 1의 과정을 거친다. 따라서 앞에서 구한 결과값을 저장해 두었다가 후에 사용하는 것!

먼저, 2 또는 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼는 연산을 수행한다. 

  • dp[i] = dp[i-1] + 1 에서 +1을 해주는 이유는 연산 횟수를 증가 시키는 것이기 때문
  • 그리고 나서 dp[i]가 2와3으로 나누어 떨어지는 경우에는 dp[i](1을 빼는 경우)와 dp[i//2or3] + 1(나누었을 경우) 중 최솟값을 선택한다.

주의 할 점은 범위를 정확하게 잘 지정해 줘여한다. index를 1부터 계산하기 위해서 범위를 <= n or < n+1 을 하는 것을 헷갈리지 말자!

코드 구현

# 1 <= n <= 1000000
n = int(input())

# DP 테이블 초기화
# 연산 횟수를 저장하는 배열
d = [0] * 1000001 # 1번 인덱스부터 시작 가능

# 다이나믹 프로그래밍 진행(bottom-up)
for i in range(2, n+1): # 2부터 n까지 각 숫자에 대해 반복
	# 현재의 수에서 1을 빼는 경우
	d[i] = d[i-1] + 1 # +1 은 연산 횟수 1 증가의미
	# 현재의 수가 2로 나누어 떨어지는 경우
	if i % 2 == 0:
		d[i] = min(d[i], d[i//2] + 1)
	# 현재의 수가 3으로 나누어 떨어지는 경우
	if i % 3 == 0:
		d[i] = min(d[i], d[i//3]+1)
# n을 1로 만드는 데 필요한 최소 연삿 횟수
print(d[n])

이 문제를 해결하기 위해, DP 테이블을 사용하여 작은 문제부터 차근차근 큰 문제로 나아가며, 각 숫자를 1로 만드는 최소 연산 횟수를 저장해 나간다. DP 테이블은 이러한 연산 횟수를 저장하는 배열이다. 

d = [0] * 1000001 # DP 테이블을 초기화, 실제 계산은 1번 인덱스부터 시작

bottom-up 방식은 작은 문제들의 해를 바탕으로 점차 큰 문제의 해를 구해나가는 방식. 이를 통해 반복적으로 동일한 계산을 줄이고, 최종적인 문제의 해를 효율적으로 구할 수 있다.

print(d[1:11])
[0, 1, 1, 2, 3, 2, 3, 3, 2, 3]
print(d[10])
3

C++

처음에 DP테이블을 선언 할 때, 고정 배열을 사용했었다. int dp[100001] = {0, }; 하지만 런타임 오류가 발생했다. 정확한 이유는 모르겠지만, 1차원 벡터로 선언하니 정답이 됐다. vector<int> dp(n+1);. 아무래도 dp배열의 크기가 너무 커서 인듯하다. 그래서 n의 크기만큼 초기화 하는것이 고려 사항인것 같다. 

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

vector<int> dp;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> dp(n + 1); // 동적 배열 선언

	dp[1] = 0;
	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];

}

DP테이블에는 index에 해당하는 각각의 수가 1을 만들기 위해 필요한 최소 연산 횟수가 저장된다.

728x90