[CLASS 3]백준 9095번, 9375번, 9461번, 11399번

9095번 : 1, 2, 3 더하기

 

아.. ㅠㅠ 이게 뭐라고 고민했을까... 종이에 써보면 바로 알 수 있는데 종이 안쓰고 머리로만 어찌 해보려다가 괜히 시간만 날렸다.

 

dp라는 것은 바로 알 수 있고, 규칙성을 찾는 것이 중요하다.

 

4 이상의 수에 대해서 그 수를 1,2,3 의 합으로 만들 수 있는 모든 조합은 그 수 - 1 , 그 수 - 2, 그 수 - 3 을 만들 수 있는 경우의 수의 합이다. 그냥 간단하게 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 인 것이다!

 

왜냐하면, 그 수 - 1 의 모든 경우의 앞, 뒤에 +1을 해주고, 그 수 - 2 의 모든 경우의 앞 뒤에 +2를 해주고, 그 수 - 3의 모든 경우의 앞 뒤에 +3을 해주는 경우의 수 만큼이 구하려는 수의 경우의 수 이기 때문이다. 결국 코드는 간단하다.

 

내 코드:

dp = [0,1,2,4] + [0] * 7
for i in range(4,11):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for _ in range(int(input())):
    print(dp[int(input())])

dp[0] = 0 은 그냥 인덱스와 요구하는 수를 맞추기 위해 넣은 것이다.

 

9375번 : 패션왕 신해빈

처음에는 딕셔너리를 하나 만들어서 각각 추가하는 방법을 생각했고, 작성했다.

 

내 코드(메모리 초과):

import sys
from itertools import product
input = sys.stdin.readline

def find():
    dict = {}
    for _ in range(int(input())):
        inpt = input().split()
        # 그 분류의 옷을 처음 입력한 경우
        if inpt[1] not in dict.keys():
            # 해당 분류의 옷을 입지 않는 경우 Nope 추가
            dict[inpt[1]] = ['Nope']
        dict[inpt[1]].append(inpt[0])
    
    allWears = []
    for wear in dict.values():
        allWears.append(wear)

    return allWears

for _ in range(int(input())):
    
    # 데카르트 곱 - 1(알몸) -> 출력
    print(len(list(product(*find())))-1)

저번에 새로 배운 itertools의 product를 사용해서 작성해봤다. 이러면 답이 잘 나오기는 하는데, 메모리 초과가 뜬다. 그도 그럴 것이, 모든 경우를 출력하는게 아니라 수만 구하면 되기 떄문에 이렇게 작성할 필요가 없다. 다시 작성한 코드는 다음과 같다.

 

내 코드:

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    w = {}
    for _ in range(int(input())):
        inpt = input().split()
        if inpt[1] not in w.keys():
        	# 해당 분류의 옷을 입지 않을 경우 1 추가
            w[inpt[1]] = 1
        w[inpt[1]] += 1
    
    a = 1
    for value in w.values():
        a *= value
    
    print(a-1)

해당 분류를 입지 않는 경우를 생각해서 1을 넣어주는것만 잊지 않았다면 쉽게 풀 수 있다. 그리고 마지막에 모든 의류를 입지 않아 알몸인 경우 1만 빼고 출력해준다.

 

9461번 : 파도반 수열

 

처음 보고 규칙성 찾기 엄청 힘들 줄 알았는데, 기초 문제라 그런지 별로 어렵지 않았다. 그냥 P(N)을 구하고 싶다면 P(N-1) + P(N-5)를 하면 된다. 코드도 쉽게 작성할 수 있다.

 

내 코드:

req = []
for _ in range(int(input())):
    req.append(int(input()))

dp = [0,1,1,1,2,2]
if max(req) > 5:
    dp += [0] * (max(req) - 5)

    for i in range(6,max(req)+1):
        dp[i] = dp[i-1] + dp[i-5]

for r in req:
    print(dp[r])

 

11399번 : ATM

(우리학교에 ATM이 하나밖에 없어서 다행이다 ㅋㅋㅋ)

 

음.. 뭐랄까 너무나도 간단한 문제이다. 그냥 걸리는 시간이 적은 순서대로 줄을 세우면 자동으로 최단시간이 되고, 이를 잘 더해서 출력하기만 하면 된다. 이게 왜 실버 3일까..

 

내 코드:

_,li = input(),sorted(list(map(int,input().split())))
t = 0
total = 0
for p in li:
    t += p
    total += t

print(total)