[홀로 하는 코딩 공부] 부녀회장이 될테야 (Python)

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 처음에 문제를 보고 단순히 이전 층에서 i호까지 더하는 for문을 사용하여 완전탐색으로 계산 하면 된다고 생각했다. 그런데 문제 조건 중에 시간 제한이 0.5초 라는거 보고 완전탐색이 아닌 dp를 사용해야겠다는 생각이 들었고 바로 규칙을 찾으려 했다.

▶ 규칙은 어렵지 않았다. a층 b호는 a-1층 1~b호까지의 합을 구하면된다. a층 b-1호는 a-1층 1-(b-1)호까지의 합이므로 a층 b호는 a층 b-1호 + a-1층 b호이다. 즉, dp[a][b] = dp[a][b-1] + dp[a-1][b]이다. 

 

import sys
input = sys.stdin.readline

T = int(input())
MAX_VALUE = 15
dp = [[i for i in range(1, MAX_VALUE+1)] for _ in range(1, MAX_VALUE+1)]

for a in range(1, MAX_VALUE):
    for b in range(1, MAX_VALUE):
        dp[a][b] = dp[a][b-1] + dp[a-1][b]

for _ in range(T):
    k, n = int(input()), int(input())
    print(dp[k][n-1])

 

 

▶ dp는 규칙만 찾으면 된다. 이 문제는 규칙이 단순했어서 규칙을 금방 찾을 수 있었다. 하지만 문제의 난이도에 따라 규칙 찾는 시간이 많이 소요된다. 다양한 dp 문제를 접해보면서 규칙 찾는 연습을 지속적으로 해야겠다. 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.