[백준/Python] 1138. 한 줄로 서기 & 6236. 용돈 관리

 

1. 백준 1138. 한 줄로 서기  

https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

 

import sys
input = sys.stdin.readline

n = int(input())
nums = [0] + list(map(int, input().split()))
ans = [0] * n

for j in range(1, n+1):
    i = 0
    pass_i = 0
    while True:
        # 해당 자리에 이미 저장된 값이 있으면 패스
        if ans[i + pass_i] != 0:
            pass_i += 1
        # 아직 i값이 올 자리가 아니면 += 1
        elif i != nums[j]:
            i += 1
        # 자리를 찾으면 값 입력
        elif i == nums[j]:
            ans[i + pass_i] = j
            break

for a in ans:
    print(a, end=' ')

• 구현 문제였는데 생각한 풀이법으로 잘 해결이 되어 매우 기뻤다.
• 비교적 빨리 문제를 해결하기도 했다!

 

---

 

2. 백준 6236. 용돈 관리  

https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
money = []

for _ in range(n):
    money.append(int(input()))

L = max(money)
R = sum(money)

while L <= R:
    Mid = (L + R) // 2
    current = Mid
    cnt = 1
    for each in money:
        if each <= current:
            current -= each
        else:
            cnt += 1
            current = Mid - each

    if cnt > m:
        L = Mid + 1
    else:
        R = Mid - 1

print(L)

• 문제 설명이 좀 ... 이해가 잘 안됐다.
• 그래도 생각해보면서 이분탐색 문제라는 감은 잡았으나, 풀이를 하기 너무 힘들었다.
• 역시나 이분탐색 개념을 한 번 공부하고, 문제 이해도 제대로 하고 접근하니 풀 수 있었다.
• 앞으로도 이분탐색 문제를 또 만나면 잘 구현할 수 있길.......