python알고리즘 익히기 -2주차

오늘은 규칙있을때 자주 쓰이는 알고리즘인 다이내믹 프로그래밍을 공부했었다.

예전에는 그냥 무대포로 풀었는데 확실히 알고리즘을 알고 푸니 쉬워졌다

동적계획법

말이 굉장히 어려운데 쉽게 말하면 내가 현재 해결해야하는 문제를
작은 문제로 나누어서 규칙을 찾아 문제를 해결하는 것

백준 문제들 및 풀이

9461번 문제 및 풀이

9461번 문제 사이트

위에 문제를 보면
1+1 = 2 
1+2 = 3
1+3 = 4
2+3 = 5 
처럼 arr[i-2] + arr[i-3]을 더한 결과가 arr[i]라는 결과가 나왔습니다. 

그래서 N의 개수가 100이 최대여서 arr[101]로 설정 해둔 뒤 전부 값을 넣어서 결과만 가져와서 출력했습니다.

arr =[0 for i in range(101)]

arr[1] = 1
arr[2] = 1
for i in range(3,len(arr)):
    arr[i] = arr[i-2] + arr[i-3]
n=int(input())
for i in range(n):
    k = int(input())
    print(arr[k])

1463번 문제 및 풀이

이 문제는 두가지를 구분 하면 된다고 생각한다

10을 보면 10 -> 5 -> 4 -> 2 -> 1 처럼 4번 카운팅 할 수도 있지만
		 10 -> 9 -> 3 -> 1 처럼 1을 먼저 빼고 카운팅하면 3번만 카운팅 하면 된다.
         
즉 1을 빼고 카운팅 한 값과 3이나 2로 나누고 카운팅 한 값 중 최소를 구하면 된다

1을 뺀 값은 9의 카운팅 값 + 1과 같다!!
고로 숫자들의 카운팅 값을 구하면  10의 카운팅 값을 구하기 쉬워진다!

이 문제의 경우 처음에는 10의 6승을 전부 메모이제이션 했는데 0.15초여서 이거 하다 시간 다갔다...

그래서 n의 숫자 만큼만 돌리게 설정했더니 되더라..

n = int(input())

arr= [0 for i in range(n+1)]

for i in range(2,len(arr)):
   arr[i] = arr[i-1]+1
   if i % 3==0:
       arr[i] = min(arr[i], arr[i//3]+1) 
       # arr[[i//3]을 하고 +1을 하는 이유는 나누기 3을 하는거니까 카운팅 숫자를 1을 추가한것이다
   if i % 2==0:
       arr[i] = min(arr[i], arr[i//2]+1)

print(arr[n])