20200525 알고리즘

1. 가장 높은 탑 쌓기

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오.

(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

▣ 입력설명 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높 이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속 적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

▣ 출력설명 첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

▣ 입력예제 1

▣ 출력예제 1

Solution

import sys

sys.stdin = open("review_input.txt", "rt")

if __name__ == '__main__':
    n = int(input())
    inputs = list()
    for _ in range(n):
        area, height, weight = map(int, input().split())
        inputs.append((area, height, weight))

    dy = [0] * n
    res = 0

    inputs.sort(key=lambda x: -x[0])
    for i in range(n):
        max_h = 0
        for j in range(i):
            if inputs[j][2] > inputs[i][2] and dy[j] > max_h:
                max_h = dy[j]
        dy[i] = max_h + inputs[i][1]
        res = max(res, dy[i])n
        
    print(res)

2. 알리바바와 40인의 도둑

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다.

알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다.

해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다. 즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요.

만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면

(1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다.

▣ 입력설명 첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다. 두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.

▣ 출력설명 첫 번째 줄에 (1, 1)출발지에서 (N, N)도착지로 가기 위한 최소 에너지를 출력한다.

▣ 입력예제 1

▣ 출력예제 1

Solution1 (Bottom-Up)

import sys
sys.stdin = open("review_input.txt", "rt")

if __name__ == '__main__':
    board = [list(map(int, input().split())) for _ in range(n)]
    dis = [[0] * n for _ in range(n)]
    dis[0][0] = board[0][0]
    for i in range(1, n):
        dis[i][0] = dis[i-1][0] + board[i][0]
        dis[0][i] = dis[0][i-1] + board[0][i]

    for y in range(1, n):
        for x in range(1, n):
            dis[y][x] = min(dis[y-1][x], dis[y][x-1]) + board[y][x]

    print(dis[n-1][n-1])

Solution2 (top-down)

import sys
sys.stdin = open("review_input.txt", "rt")

def DFS(x, y):
    if dis[y][x] > 0:
        return dis[y][x]
    if x == y == 0:
        return board[0][0]
    else:
        if y == 0:
            dis[y][x] = DFS(x-1, 0) + board[y][x]
        elif x == 0:
            dis[y][x] = DFS(0, y-1) + board[y][x]
        else:
            dis[y][x] = min(DFS(x, y-1), DFS(x-1, y)) + board[y][x]
        return dis[y][x]

if __name__ == '__main__':
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    dis = [[0] * n for _ in range(n)]
    print(DFS(n-1, n-1))

Solution3

import sys
sys.stdin = open("review_input.txt", "rt")

def DFS(x, y, sum):
    global res
    if x == y == n - 1:
        if res > sum:
            res = sum
    else:
        for i in range(2):
            xx = x + dx[i]
            yy = y + dy[i]
            if xx < n and yy < n and dis[yy][xx] > sum + board[yy][xx]:
                dis[yy][xx] = sum + board[yy][xx]
                DFS(xx, yy, sum + board[yy][xx])

if __name__ == '__main__':
    n = int(input())
    MAX = n * n * 10
    board = [list(map(int, input().split())) for _ in range(n)]
    dis = [[MAX] * n for _ in range(n)]
    dx = [0, 1]
    dy = [1, 0]
    res = 2147000000
    dis[0][0] = board[0][0]
    DFS(0, 0, board[0][0])
    print(res)

Written by@[HongDongUk]

공부한 것을 소소하게 적는 블로그.

GitHub Facebook