문제풀이/백준
[python/파이썬] 백준 2775 - 부녀회장이 될테야(브1)
bbugi
2023. 1. 29. 15:00
https://www.acmicpc.net/problem/2775
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
다이나믹 프로그래밍
다이나믹 프로그래밍 : 필요한 계산 값을 저장해두었다가 재사용 하는 알고리즘 설계 기법
● top-down 방식
큰 문제부터 시작해서 작은 문제로 분할해 가면서 푸는 것
● bottom-up 방식
작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것
● 메모이제이션(캐싱)
동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법
메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식
● 타뷸레이션
메모이제이션은 결과가 필요해질 때 계산한다면, 타뷸레이션은 필요하지 않은 값도 미리 계산해둔다.
----
아직까지 개념을 모르겠다.
알고리즘, 자료구조 등 이론을 다시 공부할 것
----
문제 이해를 어렵게 해서 k-1층의 호수만 더하면 되는 것을
0층~k-1층까지 더하는 것으로 몇날 며칠 고민하다 풀고나서
문제를 다시 읽고 제대로 이해했다..
앞으로 문제 풀 때 제대로 읽고 나서 풀 것
[정답 코드]
import sys
input = sys.stdin.readline
test_case = int(input())
for i in range(test_case): # 테스트 케이스만큼 입력 반복
k = int(input()) # 층
n = int(input()) # 호수
# 아파트 층별 1호 거주민 수 = 항상 1명이므로 배열 생성을 1로 생성
apt = [[1] * n for _ in range(k+1)]
# print(apt)
# 아파트 0층의 거주민 수
apt[0] = [i for i in range(1, n+1)]
# print(apt)
def sum_kn(floor, ho):
sum_ho = 0
for i in range(ho+1):
sum_ho += apt[floor-1][i]
# print(sum_ho)
return sum_ho
# # 아파트 k층 n호 거주민 수 = k-1층의 1호~n호 까지의 거주민 수 합
for i in range(1, k+1):
for j in range(1,n):
apt[i][j] = sum_kn(i,j)
# print(apt)
print(apt[k][n-1])
[문제 잘못 읽어서 푼 코드]
k층 거주민을 0층~k-1층의 n호까지의 거주민은 모두 합쳐야 한다고 했을 때의 풀이
import sys
input = sys.stdin.readline
test_case = int(input())
for i in range(test_case): # 테스트 케이스만큼 입력 반복
k = int(input()) # 층
n = int(input()) # 호수
# 배열 만들기
apt = [[0] * n for _ in range(k+1)] # 0층부터 k층까지 나와야 하므로 k+1범위
# print(apt)
# apt[0] = [1, 2, 3, 4]
# print(apt)
apt[0] = [i for i in range(1,n+1)] # apt[0] = [1, 2, 3, 4]
# print(apt)
# k층 1호는 2**k-1명이 산다
for i in range(1,k+1): # 인덱스범위를 k+1까지 잡아줘야 k까지 출력됨
apt[i][0] = 2**(i-1)
# print(apt)
# k층 n호는 (k층n-1호의 거주민 수) + (k-1층까지의 n호 거주민수의 합)
# apt[0][n] + apt[1][n] + apt[k-1][n]
def sum_kn(floor, ho):
sum_n = 0
for i in range(floor): # 0부터 k-1까지 범위
sum_n += apt[i][ho]
# print(sum_n)
return sum_n # for문 바깥에서 합쳐진 상태로 return 되도록 위치 잘 맞추기
# apt[k][n] = apt[k][n-1] + apt[0~k-1][n]
for i in range(1, k+1):
for j in range(1, n):
# apt의 1층의 2호는
apt[i][j] = apt[i][j-1] + sum_kn(i,j)
print(apt)
print(apt[k][n-1])