DHistory

문제 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 """ 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 길이가 L인 테이프를 가지고 있다. 물을 막을 때, 그 위치와 좌우 0.5만큼 간격을 줘야 물이 새지 않는다. 물이 새는 곳의 위치와, 테이프의 길이가 주어졌을 때 필요한 테이프의 최소 개수를 구하시오. 테이프를 자를 수 없고, 겹쳐서 붙이는 것도 가능한다. 4 3 1 2 4 5 2 """ n, l = map(int, input().split()) pipes = list(map(..

문제 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 """ N: 도시 개수 일직선 도로 위에 있다. 제일 왼쪽 도시에서 제일 오른쪽 도시로 자동차를 이용하여 이동 인접한 두 도시 사이의 도로는 길이가 다를 수 있다. (단위는 km) 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용 각 도시에는 하나의 주유소가 있다. 도시마다 리터당 가격이 다름. === example === 4 2 3 1 5 2 4 1 1번 도시에서 2km를 넣고 달린다. => 5 * 2 = 10 2번 도시에서 4..

문제 17262번: 팬덤이 넘쳐흘러 선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬 www.acmicpc.net 풀이 학교에 간 뒤 최소 시간동안 머물다가 모든 팬들과 한 번 씩 인사를 하고 학교를 떠남. === example === A: 1, 2, 3, 4 B: 2, 3, 4 C: 2, 3, 4, 5 => 학교에 가자마자 한번에 인사할 수 있음. A: 1, 2, 3, 4 B: 5, 6 => 4, 5 (학교에 머무는 시간의 총 합은 1) A에게 인사 후 B에게 인사하기 위해 시간이 필요함. """ import sys n = int(sys.stdin.readline()..

문제 2865번: 나는 위대한 슈퍼스타K 첫째 줄에 N, M, K가 주어진다. (1 ≤ M ≤ 100, 1 ≤ K ≤ N ≤ 100) 다음 M개의 줄은 각 장르에 대한 참가자의 능력이 주어진다. 이 줄에는 N개의 (i, s)쌍이 주어진다. 여기서 i는 참가자의 번호, s는 그 www.acmicpc.net 풀이 """ n: 참가자 수 m: 음악 장르 심사위원은 각 장르에 대한 능력을 점수로 매긴다. (실수) 총 K명 본선 진출 각 참가자는 단 하나의 장르만 부를 수 있다. - 한 사람이 여러 장르를 부를 수 없지만 여러 사람이 같은 장르를 부를 수 있다. 능력의 합이 최대가 되도록 참가자와 장르를 선택하는 프로그램을 작성하시오. === example === 3 2 2 2 3.0 1 0.2 3 0.1 3 1..

문제 25379번: 피하자 음이 아닌 정수로 이루어진 길이 N의 배열 A = [A1, A2, · · · , AN]가 있다. 배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장 www.acmicpc.net 풀이 실제로 바꿔가며 풀이 """ A: 음이 아닌 정수 배열 인접한 두 수를 교환하는 시행을 원하는 만큼 가능 홀수와 짝수가 인접한 경우 최대 1번 등장하도록 하는 시행의 최소 횟수는? === example === A = [4, 5, 1 ,0] = [4. 0, 5, 1]이 되는 경우 홀수와 짝수가 인접한 경우 최대 1번이 됨. """ import sys from copy import deepcopy n = int(sys.stdin...

문제 1246번: 온라인 판매 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다. www.acmicpc.net 풀이 """ N: 달갈 개수 M: 고객 수 i번째 고객은 각자 달걀을 Pi 가격 이하로 살 수 있다. - 고객은 하나의 달걀만 살 수 있음. 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격과 이 때의 총 수익은? === example === 5 4 2 8 10 7 7 21 7로 책정하는 경우 8 / 10 / 7 이하인 경우 달걀을 구매하는 인원이 있다. 즉 7이 이 때의 달걀의 가장 낮은 가격이고 총 수익은 21이다. """ import sys n, m ..

문제 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 풀이 """ 8시가 될 때까지 대기 8시가 되는 순간 입구에서 커피를 받고 자리로 이동 "강호"는 커피를 하나씩 주는 역할 "손님"은 "강호"에게 팁을 줌 팁: 커피를 몇 번째 받는지에 따라 정해짐 (원래 주려고 했던 돈 - 받은 등수 + 1) 단, 음수인 경우 받을 수 없음 === example === 민호: 3원 재필: 2원 주현: 1원 민호 => 3 - 1 + 1 = 3 재필 => 2 - 2 + 1 = 1 주현 => 1 - 3 + 1..

문제 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 """ 뉴클레오티드: A,T,G,C TAACTGCCGAT => AGCAT / GGAAT 1, 3번째가 다르므로 Hamming Distance = 2 s1 ~ sn까지 Hamming Distance의 합이 가장 작은 새 DNA s를 구하시오. => s1 ~ sn 중 각 자리마다 가장 많이 나온 알파벳을 찾으면 됨. === example === TATGATAC TAAGCTAC AAAGATCC TGAGATAC T..

문제 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 풀이 """ 총 레벨: N 각 레벨을 클리어할 때마다 점수가 주어짐 점수는 항상 양수 플레이어 점수: 각 레벨을 클리어하면서 얻은 점수의 합 (Online raking) 레벨을 난이도 순으로 배치 - 특정 레벨의 점수를 감소하여 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 함. - 점수를 내리는 것을 최소한으로 하는 방법? """ n = int(input()) scores = [] for _ in range(n): scores.append(int..

문제 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 """ 기타줄의 개수: N 브랜드 개수: M 각 줄은 6개 패키지 가격 / 낱개 가격 기타줄 N개를 사는데 최소한의 비용은? (N개를 오버해서 구매하지만 값이 싼 경우가 있을 수 있다.) """ n, m = map(int, input().split()) brands = [] for _ in range(m): package, ea = map(int, input().split()) brands.append((package, ea)) def soluti..