그냥 코딩하는 사람의 블로그

문제 설명

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

풀이 과정

1. 일반적인 BFS는 상하좌우인데 이번 케이스는 대각선까지 고려해야 하는 경우
   • 전체 2차원배열 루프를 돌면서 [i][j] = 1이 될 때를 찾는다.
   • [i][j]부터 시작하여 연결된 모든 섬들의 값을 0으로 조정해준 다음, 섬의 개수를 1개 늘려준다.
   • 전체 배열을 돌때까지 반복
2. 섬의 개수를 출력해주면 된다.

소스 코드

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

def bfs(graph, x, y):
    queue = deque([[x, y]])
    graph[x][y] = 0
    # 상하좌우
    dx = [-1, 1, 0, 0] 
    dy = [0, 0, 1, -1]

    # 대각선
    dx2 = [1, 1, -1, -1]
    dy2 = [-1, 1, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            # 상하좌우
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx and nx < len(graph) and (
                0 <= ny and ny < len(graph[0])
            ):
               if graph[nx][ny] != 0:
                   graph[nx][ny] = 0
                   queue.append([nx, ny])
            # 대각선
            nx, ny = x+dx2[i], y+dy2[i]
            if 0 <= nx and nx < len(graph) and (
                0 <= ny and ny < len(graph[0])
            ):
                if graph[nx][ny] != 0:
                    graph[nx][ny] = 0
                    queue.append([nx,ny])


while True:
    w, h = map(int, input().rstrip().split())
    if w == 0 and h == 0:
        break

    graph = [list(map(int, input().rstrip().split())) for _ in range(h)]
    answer = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                answer += 1
                bfs(graph, i, j)
    print(answer)

문제 설명

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이과정

1. 문자열들을 순차적으로 스택에 넣으면서 비교
   • 스택의 길이가 n이라고 하고, 폭발 문자열의 길이가 k라고 할때
   • 스택[n-k] ~ 스택[n]이 폭발 문자열인지 확인한다.
   • 폭발 문자열이라면, 스택에서 pop해주고 폭발에 의해 또다시 폭발 문자열 확인
   • 폭발 문자열이 아니라면, 비교과정 종료
2. 스택이 비어있다면 'FRULA', 스택에 요소가 있다면 해당 요소를 출력해주면 된다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

string = input().rstrip()
boom = input().rstrip()

stack = deque()
for s in string:
    stack.append(s)
    while True:
        if len(stack) < len(boom):
            break
        length_s = len(stack)
        length_b = len(boom)
        flag = False
        for i in range(len(boom)):
            if boom[i] == stack[length_s-length_b+i]:
                pass
            else:
                flag = True
                break

        if flag:
            break
        else:
            for i in range(len(boom)):
                stack.pop()
if stack:
    print("".join(stack))
else:
    print("FRULA")

문제 설명

문제

백준 문제 풀이에 힘들어하는 수진이를 위해 민우는 문제해결에 도움이 되는 고무오리를 준비했다. 민우가 준비한 고무오리는 신비한 능력이 존재하는데, 최근에 풀던 백준 문제를 해결해주는 능력이다. 신비한 고무오리와 함께 수진이의 백준 풀이를 도와주자!

고무오리의 사용법은 다음과 같다.

• "고무오리 디버깅 시작" 이라고 외친다
• 문제들을 풀기 시작한다
• 고무오리를 받으면 최근 풀던 문제를 해결한다
• "고무오리 디버깅 끝" 이라고 외치면 문제풀이를 종료한다.

하지만 고무오리에는 치명적인 문제가 있는데, 풀 문제가 없는데 사용한다면 고무오리는 체벌로 두 문제를 추가한다는 점이다.

입력

첫 번째 줄에 "고무오리 디버깅 시작"이라고 주어진다. 두 번째 줄부터 "고무오리" 또는 "문제"가 주어진다. 이는 "고무오리 디버깅 끝"이 주어질 때까지 반복한다. 최대 102줄이 입력으로 주어진다.

출력

고무오리 디버깅이 끝날 때, 주어진 문제를 수진이가 해결하였는지 여부에 따라 남은 문제 없이 모든 문제를 해결하였으면 "고무오리야 사랑해"을 출력하고 하나라도 문제가 남았다면 "힝구"를 출력하라.

풀이 과정

1. 스택에 push / pop
   • 고무오리를 받은 경우 stack에서 pop
     • 이 때, 고무오리를 받았는데 stack이 비어있다면 문제 2개 push
   • 문제를 받은 경우 stack에 push
2. 디버깅 종료 이후 stack에 문제가 남아있다면 "힝구" 출력, 남아있지 않다면 "고무오리야 사랑해" 출력

소스 코드

import sys
from collections import deque

stack = deque()
while True:
    p = sys.stdin.readline().rstrip()

    if p == "고무오리 디버깅 시작":
        continue

    if p == "고무오리 디버깅 끝":
        break

    if p == "문제":
        stack.append(p)
    elif p == "고무오리":
        if len(stack) == 0:
            stack.append('문제')
            stack.append('문제')
        else:
            stack.pop()

if stack:
    print("힝구")
else:
    print("고무오리야 사랑해")

문제 설명

문제

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

• 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
• ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
• 상근: 근데?
• ??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
• 상근: 아? 근데 K는 어떻게 구해?
• ??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
• 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

풀이 과정

1. 학생들을 성적 순으로 순차적으로 큐에 넣어준다.
   • 큐의 길이가 K를 넘게 된다면, 큐에서 하나 빼주고, 딕셔너리에서 빼준 학생의 이름 길이의 값도 하나 빼줌.
   • 현재 넣어야 하는 학생의 이름과 길이가 같은 큐에 있는 사람들의 수만큼 정답을 늘려줌.(이 때, 딕셔너리 사용)
   • 큐에 학생을 넣어줌, 넣어줌과 동시에 딕셔너리에서 해당 학생의 이름 길이의 값을 하나 늘려 줌.
2. 정답을 출력해주면 된다.

• 이 때, 학생들을 넣을때마다 반복문으로 큐에 있는 사람들의 길이를 일일이 비교하면서 정답을 늘려주면 시간 초과가 나타나므로 딕셔너리 활용

소스 코드

import sys
from collections import deque

input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
len_count = {i:0 for i in range(2, 21)}

queue = deque()
answer = 0
for i in range(N):
    friend = input().rstrip()
    if i > K:
        t = queue.popleft()
        len_count[len(t)] -= 1
    answer += len_count[len(friend)]
    queue.append(friend)
    len_count[len(friend)] += 1

print(answer)

문제 설명

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.

깊이가 2와 3인 완전 이진 트리

상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다.

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

왼쪽 그림에 나와있는 마을이라면, 상근이는 2-1-3 순서대로 빌딩을 들어갔을 것이고, 오른쪽 그림의 경우에는 1-6-4-3-5-2-7 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.

출력

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

풀이 과정

1. 1~5번을 읽어 보면 트리의 중위 순회임을 알 수 있다. (왼쪽 자식 -> 부모 -> 오른쪽 자식)
2. 따라서, 재귀함수로 구현한다.
   • 시작 구간은 0~(2^K-1)
   • 구간의 가운데가 부모 노드이다.
   • 왼쪽 구간과 오른쪽 구간은 자식 노드이므로 레벨이 1 증가한다. 이 때, 출력은 왼쪽에서부터 오른쪽 순서이므로 왼쪽 구간부터 방문하면서 레벨 리스트에 넣어준다.
3. 각 레벨 리스트의 요소들을 출력해주면 된다.

소스 코드

import sys

K = int(sys.stdin.readline().rstrip())
nodes = list(map(int, sys.stdin.readline().rstrip().split()))

levels = [[] for _ in range(K)]

def visit(level, left, right):
    if left == right:
        levels[level].append(nodes[left])
        return

    mid = (left + right) // 2
    visit(level+1, left, mid-1)
    visit(level+1, mid+1, right)
    levels[level].append(nodes[mid])

visit(0, 0, len(nodes)-1)

for level in levels:
    print(*level)

문제 설명

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

풀이 과정

1. 투포인터 알고리즘 사용
   • left, right를 두어, 합계를 left~right까지의 합으로 지정
   • 현재 합계가 N보다 작다면 right를 늘려 구간을 넓힘
   • 현재 합계가 N보다 크거나 같다면 left를 늘려 구간을 좁힘
     • 이 때, N보다 클 때는 정답의 개수를 저장해주어야 함.
2. 저장해 둔 정답의 개수 출력

소스 코드

import sys

n = int(sys.stdin.readline())

left = 1
right = 1
sumation = 1
answer = 0
while(left <= right):
    if sumation == n:
        answer += 1
    if sumation < n:
        right += 1
        sumation += right
    elif sumation >= n:
        sumation -= left
        left += 1

print(answer)

문제 설명

문제

문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오.

각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다.

입력

첫째 줄부터 N번째 줄까지 문자열이 주어진다. (1 ≤ N ≤ 100) 문자열의 길이는 100을 넘지 않는다.

출력

첫째 줄부터 N번째 줄까지 각각의 문자열에 대해서 소문자, 대문자, 숫자, 공백의 개수를 공백으로 구분해 출력한다.

풀이 과정

1. 문자열을 입력받을 때, 얼마나 입력받을지 정해지지 않은 경우 쓰여지는 방법

    try:
        string = input()
        ...
    except EOFError:
        break

2. 위 방법으로 문자열을 입력받은 뒤, 문자 하나씩 소문자인지, 대문자인지, 숫자인지, 공백인지 검사하고 개수를 늘리면 된다.

소스 코드

import sys
N = 0

for i in range(100):
    try:
        string = input()
        lower, upper, digit, blank = 0, 0, 0, 0
        for char in string:
            if char == " ":
                blank += 1
            if char.isupper():
                upper += 1
            if char.islower():
                lower += 1
            if char.isdigit():
                digit += 1

        print("%d %d %d %d"%(lower, upper, digit, blank))
    except EOFError:
        break

문제 설명

문제

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an= bn+ cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3= b3+ c3+ d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123= 63+ 83+ 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력

이 문제는 입력이 없다.

출력

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이 과정

• a, b, c, d를 모두 전수조사
  • a, b, c, d를 2~100까지 늘려가면서 b의 3제곱 + c의 3제곱 + d의 3제곱이 a의 3제곱인지 검사한다.
  • 이 때, a, b, c, d를 크기순으로 출력해주어야 하므로 반복문을 a부터 d 순서로 진행한다.
  • 중복된 요소를 출력하지 않기 위해 b의 반복 범위를 2100라 할 때, c는 b+1100, d는 c+1~100으로 진행한다.

소스 코드

for l in range(2, 101):
    for i in range(2, l):
        for j in range(i+1, l):
            for k in range(j+1, l):
                temp = i ** 3 + j ** 3 + k ** 3
                if l ** 3 == temp:
                    print("Cube = %d, Triple = (%d,%d,%d)"%(l,i,j,k))

풀이 과정

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

풀이 과정

1. 이분 탐색으로 정답을 찾는다.
   • 현재 휴게소 위치를 오름차순으로 정렬
   • 이분 탐색으로 구할 값을 휴게소의 구간 최댓값이라고 하고, 시작점을 0, 끝점을 L로 두고 중간값일 때, 휴게소가 몇개 세워질 수 있는지 구한다.
   • 휴게소의 개수를 구할 때, 이미 휴게소가 있는 곳에 휴게소를 또 세울수 없으므로 나누어 떨어지는 경우에는 -1을 해준다.
   • 현재 구간에서 세워야 하는 휴게소의 개수 => ((휴게소[i] - 휴게소[i-1]) // 구간 최댓값)
   • 세워야 하는 휴게소의 개수를 넘기는 경우에는 시작점을 중간값+1로 조정하고, 휴게소의 개수보다 작다면 정답을 저장해둔 뒤, 끝점을 중간값-1로 조정한다.
2. 정답을 출력한다.

• 이분 탐색을 진행할 때, 시뮬레이션을 어떻게 할지를 많이 고민해보아야 할 것 같음.

소스 코드

import sys

input = sys.stdin.readline
N, M, L = map(int, input().rstrip().split())
stations = list(map(int, input().rstrip().split()))
stations = [0] + stations + [L]
stations.sort()

left = 0
right = L
answer = 0
while left <= right:
    mid = (left + right) // 2

    # simulate
    add_count = 0
    for i in range(1, len(stations)):
        dist = stations[i] - stations[i-1]
        if dist > mid:
            add_count += (dist // mid)
            if dist % mid == 0:
                add_count -= 1
    if add_count > M:
        left = mid + 1
    else:
        answer = mid
        right = mid - 1

print(answer)

문제 설명

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 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를 출력한다.

풀이 과정

1. 인출할 금액 K의 최소 금액을 N일동안 사용할 금액 중 최댓값으로 하고, 최대 금액을 10000 * 100000으로 하여 이분탐색 진행
   • 이유는, 적어도 한번에 인출한 금액이 매일매일 사용하는 금액보다는 커야 하기 때문이다.
   • 또한, 최대 금액같은 경우는 매일매일 10000원씩 10만일(N) 사용하는데, 인출을 한번만 하는 경우에는 10000 * 100000원 인출하여야 하기 때문이다.
2. 이분탐색 진행 시 중간값으로 시뮬레이션 한다.
   • 중간값 기준으로 M번 이하 인출하는지 확인하고, 그렇다면 정답에 저장해두고 왼쪽 구간 진행
   • M번 이상 인출한다면, 오른쪽 구간 진행
3. 저장해둔 정답을 출력하면 된다.

소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
moneys = [int(input().rstrip()) for _ in range(N)]
mx_moneys = max(moneys)

left = mx_moneys
right = 10000 * 100000

answer = 0
while left <= right:
    mid = (left + right) // 2
    days = 1
    p = mid
    for money in moneys:
        if p - money < 0:
            p = mid
            days += 1
        p = p - money

    if days <= M:
        answer = mid
        right = mid-1
    else:
        left = mid+1

print(answer)