DHistory

문제 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 풀이 """ 친구 N명에레 롤케이크 1개씩 롤케이크 길이 A1, A2, ..., An 길이가 10인 롤케이크만 먹는다. 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만든다. 1. 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다. 2. 0보다 크고, x보다 작은 자연수 y를 고른다. 3. 롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다. 롤케이크를 최대 ..

문제 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net 풀이 """ N개의 물웅덩이 물웅덩이를 덮을 수 있는 길이 L 물웅덩이를 덮기 위해 필요한 널빤지의 최소 개수 === example === 3 3 1 6 13 17 8 12 끝 위치는 포함하지 않는다. 111222. // 널빤지 .MMMMM. // 웅덩이 0123456 // 좌표 """ import sys from math import ceil n, l = map(int, sys.stdin.readline().rstrip().spl..

문제 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) balls = sys.stdin.readline().rstrip()[:n] def solution(balls): r = balls.split('B') b = balls.split('R') # 전체 움직일 볼의 개수 - 왼쪽 or 오른쪽중에 있는 더 많은 동일한 볼의 개수를 제거 (움직이지 않음) return min( balls.count..

문제 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 풀이 """ 여는 괄호와 닫는 괄호만 이루어진 문자열이 주어진다. 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하시오. 안정적인 문자열이란? 1. 빈 문자열은 안정적이다. 2. S가 안정적이라면 {S}도 안정적인 문자열이다. 3. S와 T가 안정적이라면, ST도 안정적이다. 연산은 여는 괄호 => 닫는 괄호 / 닫는 괄호 => 여는 괄호 """ import sys def solution(line): if not line: return 0 queue..

문제 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 """ L과 R이 주어진다. L보다 크거나 같고, R보다 작거나 같은 자연수 중 8이 가장 적에 들어있는 수에 들어있는 8의 개수는? 108 208 각 자리수에서 8이 나오지 않을 수 있는지 확인 48880 38808 """ l, r = input().split() def solution(l, r): if len(r) > len(l): return 0 carry_bit = False answer = 0 for i, j in zip(l, r): if not carry_bit and ..

문제 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 풀이 """ 자연수 n장 i번 카드에는 ai가 쓰여있다. 카드 합체 과정 1. x번 카드와 y번 카드를 골라 두 장에 쓰여진 수를 더한 값을 계산한다. (x != y) 2. 계산한 값을 x번 카드와 y번 카드 두 장 모두 덮어 쓴다. 총 m번 하면 놀이가 종료된다. m번 후 n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수이다. 이 점수를 가작 작게 만드는 것이 놀이의 목표이다. 1 2 3 4 3 3 3 4 6..

문제 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 풀이 """ 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하시오. 행렬의 연산은 3x3 크기의 부분 행렬의 모든 원소를 뒤집는 것이다. 100 000 011 011 000 100 """ import sys n, m = map(int, sys.stdin.readline().rstrip().split()) matrix = [] for _ in range(n * 2): row = list(sys.stdin.readline().rstrip())[:m] matr..

문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 """ 1차 서류심사 / 2차 면접시험 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발 선발할 수 있는 신입사원의 최대 인원수 5 3 2 1 4 4 1 2 3 5 5 === 4 1 4, 2 3, 3 2, 4 1, 5 5 --- 7 3 6 7 3 4 2 1 4 5 7 2 5 6 1 === 3 o 1 4 x 2 5 x 3 6 o 4 2 x 5 7 o 6 1 x ..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 """ N개의 회의에 대하여 회의실 사용표를 만든다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져있다. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. (시작 시간과 끝나는 시간이 동일한 경우 시작하자마자 끝나는 것으로 생각한다.) 0 6 1 4 2 13 3 5 3 8 5 7 5 8 6 10 8 11 8 12 12 14 1 4 7 7 4 7 3 7 5 7 6 7 """ import sys n = int(sys.stdin..

문제 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 풀이 """ 책을 탑처럼 쌓아놓고 있다. 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 앞에 있는 책은 가장 위에 놓고 가장 뒤에 있는 책은 가장 밑에 놓아야한다. - 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다. 1 3 4 2 5 2 3 4 1 5 2 3 4 5 1 1 3 2 5 6 4 """ import sys n = int(sys.stdin.readline().rstrip()) books = [] fo..