[CLASS 3]백준 9205번, 11047번

9205번 : 맥주 마시먼서 걸어가기

 

맥주를 마시면서 페스티벌에 걸어간다는 이야기를 가지고 있는... 그런 문제이다. 그래프 탐색 dfs혹은 bfs로 풀면 된다. 먼저 bfs로 푼다면 다음과 같다.

 

내 코드(BFS):

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    convNum = int(input())
    home = tuple(map(int,input().split()))

    points = []
    for _ in range(convNum):
        points.append(tuple(map(int,input().split())))
    
    dest = tuple(map(int,input().split()))
    points.append(dest)

    queue = deque([home])
    visited = [home]

    happy = False
    while queue:
        now = queue.popleft()
        if now == dest:
            print('happy')
            happy = True
            break
        for point in points:
            if point not in visited:
                distance = abs(point[0]-now[0]) + abs(point[1]-now[1])
                if distance <= 1000:
                    queue.append(point)
                    visited.append(point)
    
    if not happy:
        print('sad')

 

별로 어렵진 않다. 그런데 이 문제는 조건이 좀 애매한 부분이 있는 것 같다. 시작하면서 맥주를 마시면서 가는건지, 아니면 50미터에서 처음으로 마시는 건지, 혹은 맥주를 다 먹지 않고 중간에 조금 남았다면 그 맥주병도 다 버리는건지 등등...

 

함수화하면 더 좋았겠지만 깨달은 뒤에는 너무 늦은 뒤였다.

 

DFS로 풀면 다음과 같다.

 

내 코드(DFS):

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    convNum = int(input())
    home = tuple(map(int,input().split()))

    points = []
    for _ in range(convNum):
        points.append(tuple(map(int,input().split())))
    
    dest = tuple(map(int,input().split()))
    points.append(dest)

    # dfs
    stack = [home]
    visited = [home]

    happy = False
    while stack:
        now = stack[-1]
        if now == dest:
            print('happy')
            happy = True
            break
        temp = list(stack)
        for point in points:
            if point not in visited:
                distance = abs(point[0]-now[0]) + abs(point[1]-now[1])
                if distance <= 1000:
                    stack.append(point)
                    visited.append(point)
                    break
        if temp == stack:
            stack.pop()

    if not happy:
        print('sad')

 

음.. DFS는 조금 지저분하다. 그래도 할 만 하다.

 

11047번 : 동전 0

 

음.. 이 문제는 그냥 간단한 그리디 문제가 아닌가..? 왜 실버 1인지 모르겠다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n, k = map(int,input().split())
coins = [0] * n
for i in range(-1,-n-1,-1):
    coin = int(input())
    if coin == k:
        print(1)
        exit()
    else:
        coins[i] = coin

coins = [coin for coin in coins if coin < k]
count, rest, i = 0, k, 0
while rest:
    need = rest // coins[i]
    count += need
    rest -= coins[i]*need
    i += 1

print(count)

 

지금 보니까 이렇게 뒤집을 필요도 없었을 꺼 같긴 하지만.. 그래도 나쁘지 않게 작성한 것 같다.