반응형
https://www.acmicpc.net/problem/2775
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
소스코드
풀이
동적 계획법 DP로 푸는 문제입니다.
먼저 0층에 거주하는 사람, i호에는 i명이 살고 있습니다. 즉, 0층에는
1호: 1명, 2호: 2명, 3호: 3명 ... 이런 식으로 사람이 살고 있습니다.
1층부터는 바로 아래층의 1호부터, 입력으로 주어지는 n호까지의 합의 사람이 해당 층 n호에 살고 있습니다.
3층, 4호에 사는 사람까지 나타내면 위와 같이 나타낼 수 있습니다.
이러한 방식으로 코드로 구현하는데, 각 층의 해당 호수에 해당 호수 -1까지의 숫자를 계속해서 더해나가야 합니다.
그렇기에
for i in range(k) : 층수
구문을 돌면서 각 층의 해당 호수에 거주하는 사람을 저장해두고,
for j in range(1,n): 호수
층수가 증가할 때마다 저장 되어 있는 값에 새로운 수를 추가해주시면 됩니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 11722번: 가장 긴 감소하는 부분 수열 (Python) (0) | 2023.04.03 |
|---|---|
| [백준 알고리즘] 11053번: 가장 긴 증가하는 부분 수열 (Python) (0) | 2023.04.03 |
| [백준 알고리즘] 1003번: 피보나치 함수 (Python) (0) | 2023.04.03 |
| [백준 알고리즘] 1463번: 1로 만들기 (Python) (0) | 2023.04.01 |
| [백준 알고리즘] 1092번: 배 (Python) (3) | 2023.04.01 |