[알고리즘] BOJ 2775 - 부녀회장이 될테야(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy 50문제 풀기

1 / 50

 

탐색 50문제 풀기

0 / 50

 

기초 동적 프로그래밍 50문제 풀기

1 / 50(NEW!)

 

투포인터 10문제 풀기

0 / 10

---

문제

2775번: 부녀회장이 될테야 (acmicpc.net)

2775번: 부녀회장이 될테야

---

문제 해결 아이디어

1층 3호에는 6명이 산다.
1층의 3호에 살려면 ? 0층의 1~3호까지 사는 숫자만큼 살아야 한다.

0층에는 0, 1, 2, 3, 4, 5, ...로 산다.
1층에는 0, 1, 3[1+2], 6[1+ 2 + 3], 6[1 + 2 + 3], ...
2층에는 0, 1, 4[1+3], 8[1+3+4], 13[1+3+4+5], ...

 

k층의 n호에 사는 사람의 수는? ==> 이전 값으로 알 수 있음. ==> DP 문제

k층의 n호에 사는 사람의 수 = k층의 1 ~ n-1호에 사는 사람의 수 + k-1층의 n호에 사는 사람의 수

---

구현

내 풀이

import sys
input = sys.stdin.readline

# n과 k의 max 값, range()에서 쉽게 접근하기 위해 +1
max_k = 1
max_n = 15 # 문제에서 정의된 최대값 사용(n <= 14)

# 테스트 케이스 수 입력 받기
t = int(input()) # Test case 수

# 테스트 케이스를 모아둘 리스트
test_cases = []

# 테스트 케이스 입력 받기
for _ in range(t) :
  k = int(input())
  n = int(input())
  test_cases.append((k, n)) # tuple 형태로 저장
  max_k = max(max_k, k)
max_k += 1

# cache 초기화
cache = [[0] * max_n for _ in range(max_k)]

# 0층 초기화
for i in range(max_n):
  cache[0][i] = i

# 1부터 k층 초기화
for k in range(1, max_k) :
  for n in range(1, max_n) :
    cache[k][n] = cache[k][n-1] + cache[k-1][n]  

for k, n in test_cases :
  print(cache[k][n])

---

메모

• 걸린 시간: 40분
• 다른 사람들 풀이는 거의 비슷해서 올리지 않았음.
  • 캐시를 먼저 초기화하고 테스트 케이스를 돌렸는데, 각 테스트케이스마다 캐시를 만들어주는 경우도 많았음.
• 이중 리스트 초기화 시 주의점
  • 다음처럼 초기화하지 않도록 주의
    • list = [[0] * 3] * 4
    • 이렇게 했는데 list[0] 바뀌면 list[1]도 같이 바뀜...(물론 다른 인덱스도)
    • 리스트를 초기화시킬 때 모든 행이 같은 객체로 인식되서 그렇다고 함
  • 다음처럼 초기화
    • [[0] * n for _ in range(k)]

---

마치며

쉬운 문제인데 이중 리스트 초기화하는 거 까먹어서 저렇게 했다가... 한참 헤맴