Baekjoon - 1, 2, 3 더하기 9095번 & 부녀회장이 될테야 2775번 Python 풀이

1, 2, 3 더하기

 

import sys
read = sys.stdin.readline

cache = [0] * 11
cache[1] = 1
cache[2] = 2
cache[3] = 4

for i in range(4, 11):
    cache[i] = sum(cache[i-3:i])

T = int(read())
for _ in range(T):
    print(cache[int(read())])

 

다이나믹 프로그래밍이다.

https://myjamong.tistory.com/302

백준 9095 파이썬 - 1,2,3 더하기 - 동적 계획법, DFS

코드는 위 블로그의 도움을 받았는데 이에 대해 설명을 적어두겠다.

로직은

이런식으로 진행이 된다.

 

해당 코드에 대한 설명은 주석으로 달아두겠다.

import sys #이거는 sys.stdin.readline을 아래줄에서 사용하기 위해 선언되었다.
read = sys.stdin.readline

#cache라는 리스트를 초기화시킨다. 1부터 10까지 경우의 수 저장.
cache = [0] * 11
cache[1] = 1
cache[2] = 2
cache[3] = 4
# 6~8번줄까지 직접 값을 할당한다. 앞서 설명한 표 로직에 기반한 것.

#4부터 10까지 경우의 수 구하기. 여기서 다이나믹 사용함.
for i in range(4, 11):
    cache[i] = sum(cache[i-3:i])
#cache[i]를 계산할 때 이전 값들인 cache[i-1], cache[i-2], cache[i-3]을 이용하여 현재 값인 cache[i]를 구함. 
#이전 값들은 이미 계산되어 있기 때문에 다시 계산하지 않고 이용하여 중복 계산을 피하며 문제를 해결할 수 있음.

#T변수에 몇번 테스트 할지 개수 입력 받음.
T = int(read())
for _ in range(T):
    print(cache[int(read())])

 

사실 다이나믹 프로그래밍의 기초 개념부터 공부해야할 것 같다. 코드 설명을 찾아보니 무슨 말인지는 알겠는데 처음부터 끝까지 내가 작성할 정도로 이해되지는 않았다..

---

부녀회장이 될테야

t = int(input()) #테스트 케이스 개수를 입력

for _ in range(t):
    floor = int(input())
    num = int(input())
    f0 = [x for x in range(1, num+1)]
    for k in range(floor): #건물의 층 수만큼 반복
        for i in range(1, num):# 건물 수를 계산하기 위해 건물 수 리스트를 돌음.
            f0[i] += f0[i-1] #현재 층의 건물 수는 이전 층까지 누적값. 현재 층 건물수+이전 층 건물수 연산.
    print(f0[-1])

이것도 구글의 도움을 받았다.

 

구글링하면서 새로 알게 된 기능들 위주로 적어보겠다. (코드 자체 흐름 설명은 주석에 있다.)

 

for _ in range(t): 여기서 변수 대신 언더바를 사용했는데 그 이유가 궁금했다.

알아보니 변수의 값을 사용하지 않을 때 사용된다고 한다. range(t)는 0부터 t-1까지 숫자를 생성하지만 반복문 내에서 사용되는 변수가 없을 땐 언더바를 사용해서 반복 횟수만큼만 반복할 때 사용한다고 한다.

for _ in range(t): 줄이 의미하는 바는 t번 반목한다는 것이다. 코드를 간단하게 만들 수 있다는 점이 새롭고 신기했다.

 

f0 = [x for x in range(1, num+1)]

이 부분은 리스트 컴프리헨션이라고 한다. 리스트를 만드는 간단하고 효율적인 방법이라고 한다.

range(i, num+i)는 1부터 num까지의 숫자를 생성하고 이  생성된 숫자들을 각각 변수 x에 할당하여 반복한다. 여러 줄의 코드가 한줄로 작성되는게 신기했다. 이렇게 간결한 코드문을 좀 자주 써보려 한다.