졍's 기술 블로그

택배 배송

티어 : Gold 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 다익스트라

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3  

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

예제 입출력

Algorithm

최단거리 - Dijkstra
1. 양방향 그래프 생성
2. Dijkstra 최단거리 구하기

Code

def dijkstra(start):
    queue = []
    # 시작 노드로 가는 최단 경로 0으로 설정
    heapq.heappush(queue, (start, 0))
    distance[start] = 0
    
    while queue:
        # 최단거리가 가장 짧은 노드 꺼내기
        now, dist = heapq.heappop(queue)
        
        # 이미 처리된 적 있는 노드인지 확인
        if distance[now] < dist:
            continue

        # 인접한 헛간으로 이동
        for i, C in graph[now]:
            cost = dist + C
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(queue, (i, cost))
    
import heapq
import sys
input = sys.stdin.readline
INF = 10e9

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
distance = [INF for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A].append((B, C))
    graph[B].append((A, C))

dijkstra(1)
print(distance[-1])

메모리: 51188KB
시간: 968ms

정수 삼각형

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입출력

Algorithm

Dynamic Programming
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + table[i+1][j])
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + table[i+1][j+1])

Code

N = int(input())
table = [[] for _ in range(N+1)]
for i in range(1, N+1):
    table[i] += list(map(int, input().split()))
    
dp = [[] for _ in range(N+1)]
for i in range(N+1):
    for j in range(i):
        dp[i].append(0)

dp[1] = table[1]
for i in range(1, len(table)-1):
    for j in range(len(table[i])):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + table[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + table[i+1][j+1])

print(max(dp[-1]))

메모리: 39060 KB
시간: 292 ms

요세푸스 문제

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 자료구조, 큐

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입출력

Algorithm

구현
1. list의 index에 해당하는 숫자 answer에 저장하고 remove
2. index의 값 K씩 증가시키며 list 비어있지 않을 때만 반복되도록 구현

Code

N, K = map(int, input().split())

nums = list(range(1, N+1))
index = K-1
answer = []
while True:
    # 현재 index의 사람 없애기
    answer.append(nums[index])
    nums = nums[:index] + nums[index+1:]
    if not nums:
        break
    index = (index + K-1) % len(nums)

print('<' + ', '.join(list(map(str, answer))) + '>')

메모리: 30840 KB
시간: 164 ms

큐

티어 : Silver 4
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 256 MB
알고리즘 분류 : 자료 구조, 큐

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입출력

Algorithm

구현 - Simulation, Queue

Code

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

N = int(input())
queue = deque()
for _ in range(N):
    orders = input().rstrip()
    
    # orders에 공백이 포함되어있으면 나누기
    if ' ' in orders:
        order, num = orders.split()
        num = int(num)
    else:
        order = orders
        
    if order == 'push':
        queue.append(num)
    elif order == 'pop':
        # 정수가 없는 경우
        if not queue:
            print(-1)
        else:
            print(queue[0])
            queue.popleft()
    elif order == 'size':
        print(len(queue))
    elif order == 'empty':
        # 비어있으면 1
        if not queue:
            print(1)
        else:
            print(0)
    elif order == 'front':
        # 큐에 정수가 없으면 -1 출력
        if not queue:
            print(-1)
        else:
            print(queue[0])
    else:
        # 큐에 정수가 없으면 -1 출력
        if not queue:
            print(-1)
        else:
            print(queue[-1])

메모리: 32452 KB
시간: 92 ms

마법사 상어와 파이어볼

티어 : Gold 4
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 구현, 시뮬레이션

문제

어른 상어가 마법사가 되었고, 파이어볼을 배웠다.

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

제한

• 4 ≤ N ≤ 50
• 0 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ ri, ci ≤ N
• 1 ≤ mi ≤ 1,000
• 1 ≤ si ≤ 1,000
• 0 ≤ di ≤ 7

예제 입출력

Algorithm

구현 - Simulation
1. 리스트에 명령들 담음
2. 모든 파이어볼 이동
    ☞ graph에 각 칸마다 존재하는 파이어볼의 개수 갱신
3. 그래프 전체를 보면서 값이 2 이상인 경우 질량, 속력, 방향 계산해 명령을 담는 리스트에 추가
    ☞ 질량이 0이면 추가하지 않음
4. K번째 명령이 끝아면 질량의 총합 구함

Code

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
graph = [[[] for _ in range(N)] for _ in range(N)]
orders = []
for _ in range(M):
    r, c, m, s, d = map(int, input().split())
    orders.append((r-1, c-1, m, s, d))
    graph[r-1][c-1].append((m, s, d))

# 상, 우상향, 우, 우하향, 하, 좌하향, 좌, 좌상향
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
for count in range(K):
    # 파이어볼 이동
    for r, c, m, s, d in orders:
        dx = directions[d][0] * s
        dy = directions[d][1] * s
        graph[r][c] = graph[r][c][1:]
        graph[(r+dx)%N][(c+dy)%N].append((m, s, d))
      
    orders = []
    for x in range(N):
        for y in range(N):
            # 파이어볼이 1개인 칸은 다음 명령에 추가
            if len(graph[x][y]) == 1:
                m, s, d = graph[x][y][0]
                orders.append((x, y, m, s, d))
            # 파이어볼이 2개 이상인 칸에서
            elif len(graph[x][y]) > 1:
                # 질량, 속력, 방향 구하기
                sum_m = 0
                sum_s = 0
                check_d = [0, 0]
                for m, s, d in graph[x][y]:
                    sum_m += m
                    sum_s += s
                    check_d[d%2] += 1
                    
                m = sum_m // 5
                # 질량이 0인 파이어볼 소멸
                if m == 0:
                    graph[x][y] = []
                    continue
                
                s = sum_s // len(graph[x][y])
                
                # 파이어볼 뱡향이 모두 홀수이거나 짝수이면 0, 2, 4, 6
                graph[x][y] = []
                if check_d[0] * check_d[1] == 0:
                    for d in range(0, 7, 2):
                        orders.append((x, y, m, s, d))
                        graph[x][y].append((m, s, d))
                else:
                    for d in range(1, 8, 2):
                        orders.append((x, y, m, s, d))
                        graph[x][y].append((m, s, d))

# graph에 있는 질량의 합 구하기
answer = 0
for x in range(N):
    for y in range(N):
        for m, s, d in graph[x][y]:
            answer += m
print(answer)

메모리: 31860 KB
시간: 1236 ms

치즈

티어 : Gold 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입출력

Algorithm

DFS - 재귀, 구현
1. 1시간마다 DFS를 이용해 치즈에 구멍이 있는지 확인
    ☞ 0으로된 덩어리가 2개 이상인 경우 구멍 존재
2. 구멍이 존재하면 구멍에 해당하는 칸의 값을 H로 변경
3. graph를 한 번씩 돌면서 현재 위치가 1인데 상, 하, 좌, 우 중 한 칸이라도 0이 존재하면 이번에 삭제되는 칸
    ☞ 해당 칸의 값을 C로 변경
4. 매 번 C의 개수와 1의 개수의 차를 확인해 0인 경우 반복문 break

Code

def dfs(x, y, replace_value):
    
    # graph 밖으로 벗어나면 False Return
    if x < 0 or x > N-1 or y < 0 or y > M-1:
        return False
    
    # 이미 방문했던 칸이거나 0이 아니면 False Return
    if visited[x][y] or graph[x][y] != 0:
        return False
    
    # 현재 위치 방문 기록
    visited[x][y] = True
    # 구멍인 경우 H로 변경
    graph[x][y] = replace_value
    
    # 상하좌우로 이동
    dfs(x-1, y, replace_value)
    dfs(x+1, y, replace_value)
    dfs(x, y-1, replace_value)
    dfs(x, y+1, replace_value)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
sys.setrecursionlimit(N*M)
graph = []
count_cheezes = 0 # 치즈가 녹기 전 치즈조각이 놓여 있는 칸의 개수
for _ in range(N):
    graph.append(list(map(int, input().split())))
    count_cheezes += graph[-1].count(1)

num = 0
while True:

    # 구멍의 값을 H로 변경
    visited = [[False for _ in range(M)] for _ in range(N)]
    for x in range(N):
        for y in range(M):
            # x, y가 0, 0이 아니면 replace 값 H로 설정
            if x > 0 and y > 0:
                dfs(x, y, 'H')
            else:
                dfs(x, y, 0)

    # 가장자리에 있는 1을 C로 변경
    count_c = 0
    for x in range(N):
        for y in range(M):
            if graph[x][y] == 1:
                # 현재 index의 상하좌우 중 한 군데라도 0이 있으면 가장자리
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nx = x+dx
                    ny = y+dy
                    # graph 밖으로 벗어나면 continue
                    if nx < 0 or nx > N-1 or ny < 0 or ny > M-1:
                        continue
                    
                    # nx, ny가 0이면 x, y를 C로 변경하고 break
                    if graph[nx][ny] == 0:
                        graph[x][y] = 'C'
                        count_c += 1
                        break
    
    # 현재 1인 칸과 없어질 칸의 차가 0이면 break
    if count_cheezes - count_c == 0:
        print(num+1)
        print(count_cheezes)
        break
    
    # C, H인 칸 모두 0으로 변경
    for x in range(N):
        for y in range(M):
            if graph[x][y] == 'C'or graph[x][y] == 'H':
                graph[x][y] = 0
    num += 1
    count_cheezes -= count_c

메모리: 33988 KB
시간: 148 ms

음식물 피하기

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

예제 입출력

Algorithm

DFS - 재귀
1. 쓰레기가 떨어져있는 곳은 1, 쓰레기가 없는 곳은 0으로 두고 graph 구현
2. (0, 0) 부터 (N-1, M-1) 까지 DFS를 이용해 덩어리 당 음식물 개수 확인
3. DFS에서 True 반환될 때마다 음식물 개수 최댓값으로 갱신

Code

def dfs(x, y):
    global count_
    
    # graph의 범위를 벗어나면 False Return
    if x < 0 or x > N-1 or y < 0 or y > M-1:
        return False
    
    # 현재 위치에 방문한 적이 있거나 음식물이 없는 곳이면 False Return
    if graph[x][y] == 0:
        return False
    
    # 현재 위치 방문 기록
    graph[x][y] = 0
    count_ += 1
    
    # 인접 노드 방문
    dfs(x-1, y)
    dfs(x+1, y)
    dfs(x, y-1)
    dfs(x, y+1)
    
    return True
    
import sys
input = sys.stdin.readline

# 입력
N, M, K = map(int, input().split())
sys.setrecursionlimit(N*M*K)
graph = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(K):
    x, y = map(int, input().split())
    graph[x-1][y-1] = 1

global count_ # 덩어리에 속해있는 노드 개수
answer = 0
for x in range(N):
    for y in range(M):
        count_ = 0
        # DFS 반환값이 True일 때만 정답 갱신
        if dfs(x, y):
            answer = max(answer, count_)
print(answer)

메모리: 35760 KB
시간: 80 ms

근손실

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.

다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트로 간주한다. 각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.

대학원생은 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고자 한다. 1일차부터 N일차까지의 모든 기간동안, 어떤 시점에서라도 중량이 500보다 작아지지 않도록 해야 한다.

예를 들어 N=3, K=4일 때, 각 운동 키트의 중량 증가량이 다음과 같다고 가정하자.

이 때 1번, 3번, 2번 순서대로 운동 키트를 적용한다고 해보자. 이 경우 운동 1일차에 대학원생은 중량이 3만큼 증가하지만 그와 동시에 하루에 중량이 4만큼 감소하기 때문에, 1일이 지난 이후에 중량은 499가 된다. 따라서 조건을 만족하지 못한다.

반면에 3번, 1번, 2번 순서대로 운동 키트를 적용한다고 해보자. 그러면 1일차부터 운동을 모두 마친 날까지의 모든 시점에 대하여 항상 중량이 500이상이 된다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 1개씩의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력하는 프로그램을 작성하시오.

위 예시에서는 모든 경우 중에서 총 4가지 경우가 조건을 만족한다.

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

예제 입출력

Algorithm

Back Tracking
1. stack에 운동 키트 추가
    ☞ stack에 들어있지 않은 숫자만 추가
2. 운동 키트 적용 직후 중량 갱신
3. 재귀함수 호출
4. 재귀함수 return되면 중량 원상복구 후 pop
5. stack의 길이가 N이 되거나 중량이 500 미만이 되면 pop먼저 할 수 있도록 구현

Code

def back_tracking(now_weight):
    global answer
    
    # stack의 길이가 N이 되거나 중량이 500 미만이 되면 POP먼저 하도록 구현
    if len(stack) == N or now_weight < 500:
        pass
    else:
        for idx in range(N):
            if idx not in stack:
                stack.append(idx)
                # 중량 계산
                now_weight = now_weight - K + weights[idx]
                # 마지막 index이고 중량이 500이상이면 answer 증가
                if len(stack) == N and now_weight >= 500:
                    answer += 1
                back_tracking(now_weight)
                stack.pop()
                now_weight = now_weight + K - weights[idx]

N, K = map(int, input().split())
weights = list(map(int, input().split()))
stack = []
global answer
answer = 0
now_weight = 500
back_tracking(now_weight)
print(answer)

메모리: 30840 KB
시간: 176 ms