[백준] 24954, 24955, 24956번: 쇼미더코드 2022년 1회차 파이썬 풀이

사용한 기술 스택들: 

 

https://www.wanted.co.kr/events/showmethecode

쇼미더코드 (Show Me The Code) : 원티드 주관 코딩테스트 대회 ('22년 1회차) | 원티드

 

쇼미 더 코드라는 2022년 4월 2일 토요일에 참가했던 코딩 테스트 대회가 있어서 풀이를 써보려고 한다. 문제는 총 3개였고 3개 다 파이썬으로 풀어서 금손 배지를 받았다. 백준 기준으로 대충 실 3~골 4 사이들의 문제였고, 마지막 문제 제외하고는 무난했던 거 같다.

 

WA! 금손

A번 물약 구매 (24954번)

코드

import sys
from itertools import permutations
input = sys.stdin.readline
n=int(input())
cost = list(map(int,input().split()))
sale = [[] for _ in range(n)]
for i in range(n):
    m=int(input())
    for _ in range(m):
        sale[i].append(list(map(int,input().split())))
a=permutations(range(0,n),n)
minimum = float('inf')
for i in a:
    cost_temp = cost[:]
    price = 0
    for j in i:
        price +=cost_temp[j]
        for k,s in sale[j]:
            cost_temp[k-1] = max(1,cost_temp[k-1]-s)
    minimum = min(minimum,price)
print(minimum)

해설

문제를 보면 알겠지만 n이 작아서 순열을 이용한 브루트 포스로 풀릴 거 같아서 permuatation을 사용해서 가능한 순열들을 만들어서 이 조합대로 풀었다. 순열을 돌아주면서 cost_temp에 저장한 가격들을 하나 살 때마다 가격을 바꾸어 준다. 살 때마다 쓴 돈을 price에 더해주고 최솟값 minimum과 비교해주면서 마지막에 최소 가격을 출력한다.

 

cost_temp[k-1] = max(1,cost_temp[k-1]-s)

물약의 가격이 내려가더라도 0 이하로 내려가지는 않는다라고 되어있기 때문에 1을 최소 가격이 되도록 설정했다.

 

B번 숫자 이어 붙이기 (24955번)

코드

import sys
import math

def DFS(s,e):
    stack = []
    visited = [False]*n
    stack.append((s,house[s]))
    visited[s] = True
    while stack:
        node,num= stack.pop()
        if node == e:
            return num
        for next_node in path[node]:
            if not visited[next_node]:
                visited[next_node] = True
                new_num = house[next_node]
                l = int(math.log10(new_num))+1
                stack.append((next_node,((num*10**l)%MOD+new_num%MOD)%MOD))    
MOD=1000000007
input = sys.stdin.readline
n,q = map(int,input().split())
house = list(map(int,input().split()))
path = [[]for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)

for _ in range(q):
    a,b = map(int,input().split())
    print(DFS(a-1,b-1))

해설

이 문제는 N, Q 제한이 1000 이하라서 아무리 많아봤자 O(Q*N^2) 즉 10^9번 반복이면 충분히 돌아간다. 길을 인접 리스트로 저장해주고 놀이마다 DFS/BFS를 돌려주면 된다. stack안에다가 (현재 위치, 이어 붙인 숫자)를 인자를 주고 돌려주고 원하는 집에 도착하면 이어 붙인 숫자 출력해주면 된다.

 

l = int(math.log10(new_num))+1
stack.append((next_node,((num*10**l)%MOD+new_num%MOD)%MOD))

 

여기서 주의할 점은 "단, 수가 너무 커질 수 있으니까, 1,000,000,007로 나눈 나머지를 출력하도록 하자." 이 부분이다. 이렇게 한다면 문자열로 엄청나게 길게 저장할 필요가 없다. 그냥 숫자를 뒤에 붙일 때마다 mod 연산을 해주면 10자리 수이상 넘어갈 이유가 없다.

(A+B) mod C = (A mod C + B mod C) mod C 인걸 이용해서 l에 있는 뒤에 붙일 수의 자릿수만큼 num에 0을 붙여주고 더하면 된다.

 

그렇게 어려운 DFS는 아니니 무난하게 풀 수 있다.

 

C번 나는 정말 휘파람을 못 불어 (24956번)

코드

# 뇌절 풀이

# import sys
# import heapq

# input = sys.stdin.readline
# MOD=1000000007
# n = int(input())
# s = input().rstrip("\n")
# ans = 0
# pos_w = []
# pos_h = []
# h_v = []
# e = [0]*(n+1)
# for k,c in enumerate(s):
#     if c == "W":
#         pos_w.append(k)
#     elif c=="H":
#         pos_h.append(k)
# for i in range(n-1,-1,-1):
#     c = s[i]
#     e[i] = e[i+1]
#     if c=="E":
#         e[i]+=1
# for h in pos_h:
#     i = e[h]
#     h_v.append([h,(pow(2,i,MOD)-i-1)])
# last_idx = 0
# for i in range(len(h_v)-2,-1,-1):
#     h_v[i][1] = (h_v[i+1][1]+h_v[i][1])%MOD
# pq = []
# for k,v in h_v:
#     heapq.heappush(pq,(k,v))
# for w in pos_w:
#     while pq:
#         k,v = heapq.heappop(pq)
#         if k>w:
#             ans+=v
#             ans%=MOD
#             heapq.heappush(pq,(k,v))
#             break
            
# print(ans)


# Modification from https://www.acmicpc.net/source/42292882
# 이 코드는 bennyws님이 쓰신 코드를 보고 감명받아서 설명하려고 가져왔습니다.
# 만약에 내려달라 하시면 내리겠습니다
import sys

input = sys.stdin.readline
MOD=1000000007
n = int(input())
s = input()
w=0
h=0
e=0
ans=0
for c in s:
    if c=="W":
        w+=1
    elif c=="H":
        h+=w
    elif c=="E":
        ans=(2*ans+e)%MOD
        e+=h
print(ans)

해설

일단은 이 문제에서 자잘하게 문제가 많이 생겼었어서 뇌절해서 9번 틀리고 맞았다.

ㅋㅋㅋㅋㅋㅋㅎㅎㅎ ㅠㅠㅠ

일단 제한이 n=200000이라 O(n^2)으로 풀려한 내 잘못이긴 하다. 나중에 heapq 쓰고 h, w 위치 저장해서 어찌어찌해서 풀었다가(이걸 설명할 수 있을지는 나도 모르겠다 ㅋㅋㅋㅋㅋ) bennyws님의 풀이를 보고 너무 감탄을 하고 말았다. 하나의 for loop으로 조건문 3개를 사용하는 풀이는 진짜 멋지다고 생각해서 설명해 보겠다.

 

import sys

input = sys.stdin.readline
MOD=1000000007
n = int(input())
s = input()
w=0
h=0
e=0
ans=0
for c in s:
    if c=="W":
        w+=1
    elif c=="H":
        h+=w
    elif c=="E":
        ans=(2*ans+e)%MOD
        e+=h
print(ans)

 

여기서 보면 코드는 아주 간단하다. 문자열 하나하나씩 돌아가면서 만약에 "W"이면 w에 하나 더해주고 "H"이면 w만큼 h에 더해준다. 여기서 w는 "w"가 될 수 있는 가짓수 h는 "wh"가 될 수 있는 가짓수, e는 "whe"가 될 수 있는 가짓수를 저장한다.

일단 "WAHEWHEE"라는 문자열을 생각하자.

1. "W"가 들어오면 w+=1 (w=1, h=0, e=0, ans=0)
2. "A"는 스킵 (w=1, h=0, e=0, ans=0)
3. "H"가 들어오면 w+=h (w=1, h=1, e=0, ans=0)
   1. 이 뜻은 "WH"를 하나밖에 못 만든다는 뜻
4. "E"가 들어오면 e+=h (w=1, h=1, e=1, ans=0)
   1. ans=(2*ans+e)% MOD의 뜻은 나중에
5. "W"가 들어오면 w+=1 (w=2, h=1, e=1, ans=0)
6. "H"가 들어오면 w+=h (w=2, h=3, e=1, ans=0)
   1. W_H_____, W_____H__, ___WH__ 3가지를 만들 수 있다
7. "E"가 들어오면 ans=(2*ans+e)% MOD, e+=h (w=2, h=3, e=4, ans=1)
   1. 여기서 ans=(2*ans+e)% MOD 하는 이유를 알아보자. 일단, 2*ans를 왜 하냐면, 이미 whee 가짓수가 n개 있다 하면 e가 하나 더 생기면 모든 whee, wheee, wheeee,... 에 e를 더 붙여서 가짓수가 두배가 되기 때문에 2를 곱해준다. 그리고, e를 더해주는 것은 그전에 있는 모든 whe에 e를 더 해줘서 답이 e 만큼 늘어난다. 그리고 다시 h만큼 e에 더해줘서 지금 whe 가짓수를 업데이트해준다
8. 7번과 마찬가지로 해주면 (w=2, h=3, e=7, ans=6)
9. 그래서 답이 6이 나온다.

진짜 코드는 간단한데 로직은 진짜 문제와 찰떡이다. 쉬워 보였으나 어렵게 풀었고 나중에 보니까 그렇게 어렵지 않았다는 슬픈 이야기다...