4장. 시뮬레이션

계단 오르기

엘리스토끼 선생님의 자녀 바나나색토끼와 당근애호가토끼는 코더랜드 초등학교를 다니고 있습니다. 코더랜드 초등학교는 산 속에 위치하고 있습니다.

오늘도 함께 등교를 하던 중 매번 반복되는 일상에 지루했던 당근애호가토끼는 계단을 바라보고서는 바나나색토끼에게 한 가지 게임을 제안합니다.

“바나나색토끼야. 나랑 게임 하나 하지 않을래?”

“그래! 심심하던 참인데 잘 됐다.”

“계단 오르기 게임을 하자! 여기 계단 아래부터 계단 꼭대기까지 오르는 게임이야. 어떻게 하는 거냐하면 각각의 계단에 일정한 점수를 써놓고 계단을 밟으면 그 계단에 쓰여져 있는 점수를 얻는 거지! 누가 더 많은 점수를 얻나 내기하자.”

승부욕이 강한 바나나색토끼는 이 게임에서 반드시 이기고 싶습니다! 바나나색토끼는 과연 이 게임에서 몇 점을 획득할 수 있을까요?

계단 오르기에는 다음과 같은 규칙이 있습니다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하세요.

• 입력 예시

6
10
20
15
25
10
20

• 출력 예시

75

• 입력
  • 첫째 줄에는 계단의 개수인 자연수 N이 주어집니다.(1 < N < 1,000)
  • 둘째 줄 부터 한 줄에 하나씩 제일 아래에 놓은 계단부터 순서대로 각 계단에 쓰여져 있는 점수가 주어집니다. 이 점수는 10,000 이하의 자연수입니다.
• 출력
  • 계단 오르기에서 얻을 수 있는 총 점수의 최댓값을 출력하세요.

N = int(input())
    
score = []
    
for i in range(N):
    score.append(int(input()))
    
one = [score[0],score[1]+score[0]]
two = [0,score[1]]

for i in range(2,N):
    one.append(two[i-1] + score[i])
    two.append(max(one[i-2] + score[i], two[i-2] + score[i]))
    

print(max(one[-1],two[-1]))

엘팡맨 생존기

코더랜드의 택배기사 엘팡맨!

과도한 업무에 지친 그는 최대한 배송하는 택배의 양을 줄이려고 합니다!

업무에 지친 엘팡맨을 도와주세요!

엘팡맨에겐 배송해야 하는 할당량인 무게(WW)와 배송해야 하는 택배의 무게의 종류(w1, w2w1,w2)가 2가지 주어집니다! 이 정보를 가지고 최소한의 택배의 개수로 할당량을 채울 수 있는지 계산해주세요!

• 입력 예시 1

250
5 8

• 출력 예시 1

32

• 입력 예시 2

17
2 4

• 출력 예시 2

-1

• 입력
  • 첫 번째 줄에 그날 배달해야 하는 할당량(WW)이 주어집니다. (2 ≤ WW ≤ 5000)
  • 두 번째 줄에 그날 배달해야 하는 화물의 무게의 종류가 두가지 (w1, w2w1,w2)주어집니다. 이 값은 반드시 작은 값이 먼저 주어집니다. (1 ≤ w1, w2w1,w2 ≤ 1000)
• 출력
  • 어떻게 해야 가장 적은 화물을 가져 갈 수 있는지 계산 한 후 그 양을 출력해주세요.
  • 정확하게 나눌 수 없다면 -1을 출력하세요.

Sum = int(input())
w1, w2 = map(int,input().split())

cnt = 0

Min = 987654321

while Sum>=0:
    if Sum % w2 == 0:
        Min = min(Min, cnt + Sum // w2)
    Sum -= w1
    cnt += 1
    
if Min == 987654321:
    print(-1)
else:
    print(Min)

모자 장수의 모자 장사!

코더랜드 시장에서 모자를 판매하는 모자 장수가 있어요. 이 모자 장수는 많은 돈을 벌어 더 많은 모자를 사기 위해 대책 없이 가진 돈을 모두 사용해 모자를 샀어요. 장사를 시작 하려고 보니 현금 밖에 받지 못 하는 모자 장수에게는 거스름 돈을 줄 돈이 전혀 없었어요!

과연 이 모자 장수는 무사히 장사를 할 수 있을까요?

모자 1개의 가격은 5원 입니다. 고객은 모자를 한 사람 당 하나씩 순차적으로 구매합니다. 코더랜드의 화폐 종류는 5원, 10원, 20원 이 3가지 입니다. 각 모자 당 5원의 가격을 정확히 지불하도록 거스름 돈을 고객에게 주어야 합니다.

• 입력 예시 1

5 5 5 5 10 20 10

• 출력 예시 1

True

• 입력 예시 2

5 5 10 10 20

• 출력 예시 2

False

• 입력
  • 각 고객들이 가진 화페들이 공백을 기준으로 제공됩니다.
  • 고객들의 수는 최소 0명에서 10,000명 사이입니다.
• 출력
  • 거스름 돈을 무사히 돌려 줄 수 있다면 True, 아니라면 False를 출력해주세요

get_money = list(map(int, input().split()))

cnt_5 = 0
cnt_10 = 0

check = True

for money in get_money:
    if money == 5:
        cnt_5 += 1
    if money == 10:
        cnt_5 -= 1
        if cnt_5 < 0:
            check = False
            break
        cnt_10+=1
    if money == 20:
        if cnt_10>0 and cnt_5>0:
            cnt_10-=1
            cnt_5-=1
        elif cnt_5>2:
            cnt_5-=3
        else:
            check = False
            break
print(check)

균형의 수호자

코더랜드 최고의 부호 OOO은 코더시티에서 가장 높은 건물을 2채 세울려고 합니다! 하지만 안타깝게도 OOO가 사용할 수 있는 건축자재는 한정적이고 두 건물 높이는 반드시 같아야 합니다!

과연 OOO은 한정된 건축 자재를 가지고 얼마나 높은 타워를 만들 수 있을까요?

• 입력 예시 1

1 3 5 7

• 출력 예시 1

8

• 입력 예시 2

1 2 4

• 출력 예시 2

재료가 부족합니다

만약 각각 1 3 5 7 이라는 길이를 가진 건축자재를 가지고 있다면 3 + 5 = 8, 1 + 7 = 8 이므로 8의 높이를 가진 건물을 2채 지을 수 있습니다!

다만, 모든 건축 자재를 꼭 사용해야 할 필요는 업습니다.

• 입력
  • 자연수로 이루어진 숫자들이 주어집니다.
  • 이 숫자의 크기는 1 보다 크거나 같으며 1000보다 작거나 같습니다.
  • 이 숫자들의 길이는 0보다 크거나 같으며 20보다 작거나 같습니다.
• 출력
  • 건물의 높이가 가장 크면서도 같을 수 있다면 그 높이를 출력하세요
  • 높이가 같을 수 없다면 “재료가 부족합니다”를 출력하세요

heights = list(map(int, input().split()))

def make_building(one, two, cnt):
    if one == two:
        global Max
        Max = max(Max, one)
    if cnt == len(heights):
        return
    make_building(one + heights[cnt], two, cnt+1)
    make_building(one, two + heights[cnt], cnt+1)
    make_building(one, two, cnt+1)

Max = 0
make_building(0,0,0)

if Max == 0:
    print('재료가 부족합니다')
else:
    print(Max)

엉망진창 다과회

모자장수와 3월의 토끼가 다과회 테이블에 배치 할 차의 위치에 대해서 몇 시간째 싸우고 있습니다. 모자장수는 홍차를 좋아하여 홍차를 더 많이 테이블 위에 올리고 싶었고 토끼는 케이크를 좋아해서 케이크를 더 많이 테이블에 올려두고 싶었기 때문인데요.

방금, 다과회에 도착한 엘리스는 싸움을 중재하기 위해 일부 칸에 있는 음식을 전부 제거하고, 그 칸을 경계선으로 두가지 영역을 나누는 방법을 떠올렸습니다!!

테이블의 크기는 직사각형이고, H x W 개의 칸으로 나누어져 있습니다. 모든 칸에는 홍차(Black Tea) 또는 케이크(Cake)가 위치해있습니다. 경계선은 가장 왼쪽 윗칸에서 출발하며, 한 칸 아래, 오른쪽, 오른쪽 아래 대각선으로 이동할 수 있다. 선은 오른쪽 아랫칸에 도착할 때까지 이동합니다.

모자장수의 홍차(Black Tea)는 선이 지나간 길의 아래쪽에 칸을 얻게 되고, 토끼의 케이크(Cake)는 위쪽의 칸을 얻게 됩니다. 따라서, 칸을 하나도 받지 못하는 경우가 생길 수도 있습니다. 엘리스는 풍족한 다과회를 위해 아래 쪽에 있는 모자장수의 홍차와 위 쪽에 있는 토끼의 케이크의 합을 크게 만드려고 합니다.

엘리스를 위해 가능한 합 중 가장 큰 합을 구하는 프로그램을 작성하세요.

• 입력 예시

4 3
C3 B2 C6
B5 C1 C4
B2 B4 B1
C1 C3 B3

• 출력 예시

21

• 입력
  • 첫째 줄에 테이블의 크기 HeighHeigh와 WidthWidth가 주어집니다. (2 ≤ Width, HeightWidth,Height ≤ 1500)
  • 둘째 줄부터 각 줄에는 각 칸에 배치되어 있는 차나 케이크의 개수가 주어집니다. 홍차는 BB, 케이크는 CC이고, 각 칸에 배치 되어 있는 개수는 1보다 크거나 같고, 99보다 작거나 같습니다.
• 출력
  • 가능한 합 중 가장 큰 것을 출력해주세요.

h,w = map(int,input().split())

table = []

b = [[0] * (w+2) for i in range(h+1)]
c = [[0] * (w+2) for i in range(h+1)]
dp = [[0] * (w+2) for i in range(h+1)]


for i in range(h):
    table.append(input().split())

for i in range(h):
    for j in range(w):
        if (table[i][j][:1] == "B"):
            b[i+1][j+1] += int(table[i][j][1:])
        else:
            c[i+1][j+1] += int(table[i][j][1:])

for i in range(1, h+1):
    for j in range(1, w+1):
        b[i][j] += b[i][j-1]
        c[i][w-j+1] += c[i][w-j+2] 

for i in range(1, h+1):
    for j in range(1, w+1):
        if (i == 1 or j == 1):
            dp[i][j] = dp[i-1][j] + c[i][j+1]
            continue
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + b[i][j-1] + c[i][j+1]
        dp[i][j] = max(dp[i][j], dp[i][j-1] - c[i][j] + c[i][j+1])

print(dp[h][w])