Total

만들 수 없는 금액

문제 N(1~1,000)개의 동전으로 만들 수 없는 양의 정수 금액 중 최솟값 출력 5 3 2 1 1 9 분석 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target 변수를 업데이트 풀이 n=int(input()) a=list(map(int, input())) a.sort() target=1 for i in a: # 만들 수 없는 금액을 찾았을 때 반복종료 if target

[5585] 거스름돈

5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 분석 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘으로 해결 가능 풀이 """ 500엔, 100엔, 50엔, 10엔, 5엔, 1엔짜리 동전이 무수히 많은 경우 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수 지불할 돈 입력 """ m=int(input()) c=[500, 100, 50, 10, 5, 1] n=1000-m cnt=0..

[1300] k번째 수 (이분탐색, 2차원 배열)

1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 분석 n=3, k=7로 가정 중앙값보다 작거나 같은 수의 개수 = 중앙값을 N으로 나눈 값 1. 최초의 중앙값 : 4 = (1+7)/2 1*1 = 1 1*2 = 2 1*3 = 3 1행 : 4/1 = 4지만 행의 크기가 3개이므로 3 2*1 = 2 2*2 = 4 2*3 = 6 2행 : 4/2 = 2 3*1 = 3 3*2 = 6 3*3 = 9 3행 : 4/3 = 1 cnt를 다 더하면 5이므로 k(7)보다 작음 => 중앙값을 증가시킴 ..

역수열

문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞 에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라 한다. 4 8 6 2 5 1 3 7의 역수열 : 5 3 4 0 2 1 1 0 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3보다 큰 수는 4, 8, 6, 5 이렇게 4개.... n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출력 첫 번째 줄에 자연수 N(3

[2343] 기타 레슨 (블루레이 만들기, 이진탐색)

2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 분석 뮤직비디오 (이분탐색, 결정 알고리즘) 문제 DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 순서가 그대로 유지되어야 한다. 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 하였다. DVD karla.tistory.com 풀이 n,m=map(int,input().split()) a=list(map(int,input().split())) start=end=0 for i in a: if startm: sta..

증가수열 만들기

문제 1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만듭니다. 이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니다. 예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다. 맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다. 첫째 줄에 자연수 N(3

침몰하는 타이타닉 (deque)

문제 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력 첫째 줄에 자연수 N(5

창고정리

문제 창고의 가로 길이와 각 열의 상자 높이가 주어집니다. 만약 가로의 길이가 7이라면 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있 으며 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다. 위에 그림을 1회 높이 조정을 하면 다음과 같아진다. m회의 높이 조정을 한 후 가장 높은 곳 과 가장 낮은 곳의 차이를 출력 10 69 42 68 76 40 87 14 65 76 81 50 풀이 l=int(input()) a=list(map(int, input().split())) m=int(input()) a.sort() for i..

씨름 선수

문제 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습 니다. 다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자 만 뽑기로 했습니다. 만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다. 지원자의 수 N(5

[1931] 회의실 배정

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net """ 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 첫째 줄에 회의의 수 n(1