9461번: 파도반 수열

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 �

www.acmicpc.net

 

<내 코드>

n = int(input())
memo = [0 for _ in range(101)]

for i in range(0, 4):
    memo[i] = 1
for j in range(4, 6):
    memo[j] = 2

for _ in range(n):
    m = int(input())
    for k in range(6, m+1):  # 6 ~ m-1
        memo[k] = memo[k-1] + memo[k-5]

    print(memo[m])

 

피보나치 수열과 비슷한 맥락으로 규칙을 찾아 점화식을 세우면 간단하게 풀 수 있었다.

인덱스 0번 ~ 4번까지는 1과 2로 넣어주고 그 다음부터는 점화식을 통해 값을 구해나가는 구조였다. 인덱스 값을 0번째 부터 설정해서 뒤에서 조금 헷갈린거 말고는 크게 어렵지 않았다.

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 1932] 정수 삼각형 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)  (0) 2020.08.23
[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21
[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18

 

 

2748번: 피보나치 수 2

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)��

www.acmicpc.net

 

<내 코드>

n = int(input())
memo = [0 for i in range(n+1)]
memo[1] = 1
for i in range(2, n+1):
    memo[i] = memo[i-1]+memo[i-2]

print(memo[-1])

처음에 재귀호출을 통해 풀었을 때, 예상대로 시간초과가 났다. 

Bottom-up은 바닥에서 올라오는 것, 즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다.

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21
[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18
[백준 11866] 요세푸스 순열 - Python  (0) 2020.08.18

+ Recent posts

티스토리툴바