Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- udemy
- 종만북
- 백준
- server
- graph
- C언어
- greedy
- BASIC
- 따배씨
- BOJ
- 따라하며 배우는 C언어
- JavaScript
- php
- BFS
- Algospot
- Cleancode
- DP
- Algorithm
- Python
- 인프런
- 따라하면서 배우는 C언어
- sorting
- 생활코딩
- Math
- C
- programmers
- dfs
- web
- 정수론
- String
Archives
- Today
- Total
몽상실현개발주의
[BOJ] 1463 / 1로 만들기 / Python 본문
[BOJ] 1463 / 1로 만들기 / Python
풀이
처음 시도는 while 문을 이용한 조건으로 작성 하였다.
X = int(input())
cnt = 0
while (1):
if X == 1:
break
if X % 3 == 0:
X //= 3
cnt += 1
elif X % 2 == 0:
X //= 2
cnt += 1
else:
X -= 1
print(cnt)
하지만, 반례인 10 에서 조건에 부합하지 않는 다는것을 생각하였다.
10 -> 9 -> 3 -> 1 이 아닌 10 -> 5 -> 4 -> 2 -> 1 이 나옴
그래서 모든 경우를 잡기 위하여 DFS 로 작성 해 보았다.
def solution(n):
def DFS(n, cnt):
global res
if n == 1:
res = min(res, cnt)
return
if n % 3 == 0:
DFS(n//3, cnt+1)
if n % 2 == 0:
DFS(n//2, cnt+1)
DFS(n-1, cnt+1)
DFS(n, 0)
print(res)
res = 123456789
X = int(input())
solution(X)
결과는 너무나도 당연하게 시간초과.
DP 문제임을 생각하고 구상해 보았지만 Memorization 을 어떻게 해야 할지 구상되지 않았고
검색을 통해 참고 하였다.
해법은 점화식 형태로 구하는 것
점화식 : dp(N) = min( dp(N//3) + 1, dp(N//2) + 1, dp(N-1) + 1)
X = int(input())
dp = [0 for _ in range(X+1)]
for i in range(2, X+1):
a = b = c = 123456789
if i % 3 == 0:
a = dp[i//3] + 1
if i % 2 == 0:
b = dp[i//2] + 1
c = dp[i-1] + 1
dp[i] = min(a, b, c)
print(dp[X])
- 시간복잡도는 for 문을 한번 순회 하므로, O(N) (역시나 DP 가 효율적이다.)
이렇게 list 를 이용하여 점화식으로 아래에서 부터 값을 채워나가는 것을 Tabulation 이라고 한다.
Memorization 과 Tabulation 의 차이 는 따로 정리 해 보았다.
참고 블로그
'Algorithm PS > BOJ' 카테고리의 다른 글
[BOJ] 10844 / 쉬운 단계 수 / Python (0) | 2021.05.10 |
---|---|
[BOJ] 9095 / 1, 2, 3 더하기 / Python (0) | 2021.05.10 |
[BOJ] 11727 / 2×n 타일링2 / Python (0) | 2021.05.10 |
[BOJ] 11726 / 2×n 타일링 / Python (0) | 2021.05.09 |
[BOJ] 입출력 기본 문제 풀이 (0) | 2021.05.06 |
Comments