[DP] 1. 백준 1463번

코딩테스트

코딩테스트 관련 알고리즘은 아래와 같다. 주로 이 아래의 알고리즘들 아래에서 문제가 출제된다 생각하고 확실하게 학습하고 지나가야 한다.

• DFS/BFS
• 이진 탐색
• DP (Dynamic Programming)
• 최단 경로: 다익스트라/플루이드 워셜
• 유니온 파인드/크루스칼/부분합/투 포인터

다이나믹 프로그래밍

다이나믹 프로그래밍은 규칙을 찾아내는 것에 집중해야 한다. 그러기 위해서는 특정 몇개의 입력값에 대한 출력값이 도출되는 과정들을 하나하나씩 적어보면서 규칙을 찾아낼 필요가 있다.

백준 1463번

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

오늘 풀어볼 문제도 위와 같은 방법으로 접근이 가능하다.

a(1) = 0
a(2) = 1 + a(1) # 2로 나누고 a(1) 값 사용
a(3) = 1 + a(1) # 3으로 나누고 a(1) 값 사용
a(4) = 1 + a(2) # 2로 나누고 a(2) 값 사용
a(5) = 1 + a(4) # 1빼면 4. 즉 4의 값을 사용하면 된다.

위의 정답 형태를 관찰하면 알겠지만, 마치 점화식의 꼴, 즉 이전의 정답값을 활용해 다음의 정답값을 도출해내는 것을 발견할 수 있다. 다만, 점화식을 세우기 위해서는 총 2가지 조건을 세워야 한다.

1) 초기값은 무엇인지 (= 탈출 조건은 무엇인지)
2) 점화식은 무엇인지

해당 문제에서 1) 초기값은 n=1일 때이다. 이때의 정답은 1이다. 2) 점화식은 n을 3으로 나누기/2로 나누기/1 빼기를 순서대로 실행해보고, 실행가능한 연산을 실행한 결과 중 가장 최솟값을 최종값으로 입력하면 된다.

# 1을 뺐을 때
d[i] = 1 + d[i - 1]
if i%3==0: # 3으로 나눴을 때
	d[i] = min(d[i],1 + d[i//3])
if i%2==0: # 2로 나눴을 때
	d[i] = min(d[i],1 + d[i//2])

이렇게 점화식과 초기겂을 설정한 후에는, a(1)부터 a(최댓값)까지 미리 계산하여 dictionary를 만든 후 특정 n값을 입력하면 바로 결과가 출력되게끔 코드를 구현하면 된다.

코드 풀이

항상 생각하자. 중요한 것은 문제를 어떻게 해결할 것인지에 대한 논리이고, 코드는 그저 이를 옮겨적는 언어일 뿐이다!

n = int(input())

d = [0] * (n+1)

for i in range(2,n+1):
	# 확실하게 가능한 연산
	d[i] = 1 + d[i - 1]
	if i%3==0:
		d[i] = min(d[i],1 + d[i//3])
	if i%2==0:
		d[i] = min(d[i],1 + d[i//2])

print(d[n])