문제풀이/백준

[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])