백준 2775번 풀이

문제

https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

특정 층, 특정 호의 아파트 거주민 수 맞추기

 

Reference

https://crazykim2.tistory.com/586

[백준알고리즘/기본 수학 1단계] 2775번 문제 : 부녀회장이 될테야

 

https://ooyoung.tistory.com/89

백준 2775번 [파이썬 알고리즘] 부녀회장이 될테야

위쪽은 언어가 달라서 어떻게 푸셨는지만 봤다.

 

풀이

일단 이 아파트의 규칙이 하나 있다. a층 b호에 입주하려면 (a-1)층의 1호부터 b호까지 사는 입주민의 총 합을 데려와야 한다. 이 아파트는 0층부터 있고, 0층 b호에는 b명의 주민들이 산다. 그러니까 내가 1층 3호에 살 거면 0충 1호+0층 2호+0층 3호 해서 6인팟 풀방으로 구해야 한다. 어디 공대 뛰러 가시나 따라서 각 층의 1호는 아래층 1호에 사는 주민 수까지만 데려오면 되므로 1인가구가 살 수 있다. 이제 그 옆부터 슬슬 가관인거지…

당장 1층 3호부터 6인 풀팟인데 층수가 올라갈수록 파티원이 기하급수적으로 늘어난다. 

아파트가 프랙탈 구조라 한 호수 안에 방이 많은가…? 어디 케라핌 잡으러 가시나

import sys
T = int(sys.stdin.readline())
for i in range(T):
    k = int(sys.stdin.readline()) # 층
    n = int(sys.stdin.readline()) # 호
    zero_floor=list(range(1,n+1))
    # 0층에는 이만큼 살아요
    for x in range(k):
        for y in range(1,n):
            zero_floor[y] += zero_floor[y-1]
    print(zero_floor[-1])

패턴이 어려워서 이거 시그마 가야 하나 했는데 그냥 쌩으로 계산해버리심… 참고로 마지막줄 print문을 맨 밖으로 빼면 틀립니다. (그렇게 내봐서 알아요…) 맨 처음 for문 밖으로 나가게 되는 거라 마지막 결과만 출력되기 때문. 참고로 밑에 x, y 들어간 for문은 구구단이랑 비슷하다.

numeric=[2,3,4,5,6,7,8,9,10]
for i in numeric:
    for j in numeric:
        print(i,"x",j,"=",i*j)

이게 구구단코드. (좀 변형됐음) 이 코드는

1. Numeric이라는 리스트 안에서
2. i번째 원소에 대해
3. j번째 원소를 싹 다 곱해서 출력해라

이런 얘기이다. 그래서 2*2부터 2*10까지 출력한 다음 3*2로 넘어간다.

for x in range(k):
    for y in range(1,n):
        zero_floor[y] += zero_floor[y-1]

이 코드도 비슷하게 돌아가는데

1. 1부터 n(호수)까지 범위가 있을 때
2. 0층의 0호부터 n호까지를 리스트 앞의 값에 더해라 (0층은 n호에 n명이 살기 때문에 그냥 리스트로 만들어주면 된다)
3. 그 더하는 걸 k만큼 반복하세요

이런 거. 참고로 각 층의 1호는 계산 범위에서 빠진다.

 

Appendix. 합의 기호, 시그마

일단 들어가기 전에 브금 하나 틀고 가자.

https://youtu.be/vOpQoAqTTpc

아 역시 클럽 시그마져.

 

시그마는 그리스어 알파벳으로, ∑ 혹은 σ라고 쓴다. 아 이거요? 일어 자판 세팅해두면 독음 맞으면 그리스어 기호 쓸 수 있다. 아무튼… 왼쪽이 대문자 오른쪽이 소문자인데 오늘 설명할 합의 기호 시그마는 대문자이고, 소문자 시그마는 통계쪽에서 모표준편차(왜 1시그마 3시그마 하는 그거)를, 화학쪽에서는 시그마 결합(S오비탈끼리 뭐 지지고 볶는듯)을 나타낸다.

시그마는 이런 식으로 쓰는데, 이건 대충 k가 1부터 n까지일 때 k를 싹 더하라는 얘기. 즉, 초항이 1이고 공차가 1인 등차수열을 싹 다 더하라는 얘기와 같다.

위는 일반적인 시그마 공식. 순서대로 k가 1부터 n까지일 때 k, k제곱, k 3승을 더하는 공식이다.

 

그래서 록맨 시그마랑 쟤랑 뭔 상관이냐고? 시그마는 록맨 X 시리즈의 최종보스(X8 빼고)이고, 시그마 체력 바에 나오는 기호가 저거(특히 X5)이다. 그리고 자주 죽어나가신다