[백준] 동작 계획법 (1)

백준 2748 피보나치 수2

문제

풀이

import sys

N = int(sys.stdin.readline())
arr = []

for i in range(N + 1):
    arr.append(i)

for i in range(2, N + 1):
    arr[i] = arr[i - 1] + arr[i - 2]

print(arr[-1])

피보나치의 수

첫째항 1, 둘째항이 1이고 그 다음항부터는

n번째의 수 = (n-1)번째의 수 +(n-2)번째의 수

숫자의 정렬을 말한다.

풀이 방법은 for 문을 이용해서 2번째숫자부터 합을 구해주면 된다.

---

백준 9461 파도반 수열

문제

풀이

import sys

n = int(sys.stdin.readline())
arr = [1, 1, 1, 2, 2, 3]

for _ in range(n):
    m = int(sys.stdin.readline())
    length = len(arr)
    if m > length:
        for l in range(length, m + 1):
            arr.append(arr[l - 1] + arr[l - 5])
    sys.stdout.write((str(arr[m - 1]) + "\n"))

처음 봤을때는 어떤식으로 반복되는지 헤매다가
하나씩 해봤다.
역시 수학은 근성이다 😁😁

삼각형을 그려봤다 한... 7번째쯤 가니까 보이기 시작했다.
하다보니까 피보나치의 수 사각형하고 비슷한거 같에서
비슷하겟다 생각 하고 보니까
n번째의 숫자가 n-1번째의 숫자와 n-5번째의 숫자의 합인게 보였고,

코드를 작성햇다.

print로 풀었는데 속도 차이가 궁금해서 sys 를 이용해서 풀고 채점을 다시 받았엇는데,
속도차이가 거의 없길래 이걸로 올렸다.

---

백준 1149 RGB거리

문제

풀이

N = int(input())
price = []
sum_price = []
i = 1
for _ in range(N):
    price.append(list(map(int, input().split())))

while i < N:

    price[i][0] = min(price[i - 1][1], price[i - 1][2]) + price[i][0]
    price[i][1] = min(price[i - 1][2], price[i - 1][0]) + price[i][1]
    price[i][2] = min(price[i - 1][1], price[i - 1][0]) + price[i][2]

    i += 1

print(min(price[N - 1]))

이 문제는 생각보다 쉬워서 금방 풀었다.

🚀 금방 푼게 30분인건 함정 😂😂😂😂😂

R의 가격 = price[i][0]

G의 가격 = price[i][1]

B의 가격 = price[i][2]

i번째 까지 색의 합은 i 번째 색의 가격 + i-1 번째까지 나머지 두숫자의 합을 구해서 그중에 가장 작은 값을 구해주면된다.

---

백준 1932 정수 삼각형

문제

풀이

N = int(input())
arr = []

for _ in range(N):
    arr.append(list(map(int, input().split())))

for i in range(N):
    if i == 0:
        continue
    elif i == 1:
        arr[i][0] = arr[0][0] + arr[i][0]
        arr[1][1] = arr[0][0] + arr[i][1]
    else:
        for j in range(len(arr[i])):
            if j == 0:
                arr[i][j] = arr[i - 1][j] + arr[i][j]
            elif i == j:
                arr[i][j] = arr[i - 1][j - 1] + arr[i][j]
            else:
                arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - 1]) + arr[i][j]
print(max(arr[N - 1]))

사실 이 문제는 문제에 있는 삼각형사진으로 보면 헷갈리는데 예제입력에 있는 숫자들을 보면
좀 더 이해가 된다.
삼각형사진으로 보면 이게 몇번째인지 헷갈렸엇는데,
아래에 예제 입력을 보고 이해했다.

j가 마지막자리 숫자일때는 경우의 수가 한가지 밖에 없기 때문에 따로 빼서 합을 구해줬다.
위에서 푼 정수 삼각형이랑 거의 똑같아서 푸는데 어려운 점은 없었다.

두 가지의 길이 있는데, 어디로 가야할지 정하는 것보다는
이 숫자가 어디서 왔는지를 생각하니까 좀 더 수월햇다.

마찬가지로 각자리의 수에는 지금까지의 합을 저장해서 마지막 줄에서 가장 큰값을 프린트해주면 된다.

---

백준 2579 계단 오르기

문제

풀이

N = int(input())
arr = []
sum_num = [0] * N
count = 0

for _ in range(N):
    arr.append(int(input()))

for j in range(len(arr)):
    if j == 0:
        sum_num[j] = arr[0]
    elif j == 1:
        sum_num[j] = arr[0] + arr[j]
    elif j == 2:
        sum_num[j] = max(arr[0] + arr[2], arr[1] + arr[2])
    else:
        sum_num[j] = max(arr[j] + sum_num[j - 2], arr[j] + arr[j - 1] + sum_num[j - 3])
print(sum_num[N - 1])

사실 처음에는 한칸이동시에 count를 해서 풀어야겠다 생각했다.

N = int(input())
arr = []
sum_num=[]
count = 0

for _ in range(N):
    arr.append(int(input()))

for j in range(len(arr)):
    if j ==0:
        continue
    elif j ==1:
        arr[j] = arr[0] + arr[j]
    else:
        while count <2:
            arr[j] = arr[j]+arr[j-1],
            arr[j] = arr[j]+arr[j-2]
            count += 1

하다 막혀서 한 2시간은 헤멘것 같다.
거꾸로 생각해보면 의외로 쉽게 풀린다.
위에거랑 비슷한 성격인데, 한참을 고민 했다....

n번째 까지 계단의 숫자 합을 구하는 문제인데, 문제는 연속해서 3번은 1칸씩 전진할 수 없다.
여기에 현재 칸의 계단 숫자를 더해서 더 큰값을 구해주면 된다.

n = n-1번째에서 왔을경우, n-2번째에서 왔을경우

그림 말고 설명

n-1에서 왔을 경우

n-2 번째에서 오면 안됨.
-> n-1의 계단숫자와 n-3까지 계단 수의 합을 구해주면 됨.

n-2번째에서 왔을 경우

n-3에서 와도 되고, n-4에서 와도됨
결국 n-2까지의 합을 구해서 현재 계단의 숫자와 합해주면 됨.

이런 식으로 두가지 경우의수를 구하면 된다.

---

블로그 이쁘게 써보고 싶어서 급하게 그려봤는데

그래도 마우스로 하는 것보단 훨씬 이쁨❤️