링크 : https://www.acmicpc.net/problem/15903 문제소요시간: 7분 42초설계하기(접근방법) 1. 입력받기입력받을 카드의 개수가 최대 100만개이다. 시간복잡도를 고려해야한다 2. 구현하기카드의 합을 가장 작게 만드는 법은, 가장 작은 카드끼리 더해서 새로운 합을 만드는 것이다누적합의 개념을 생각하면 쉽게 이해할 수 있을 것이다 해당 개념을 사용하려면 리스트의 최소 원소 2개를 추출할 수 있어야한다.일반 리스트로는 100만개의 원소를 다 처리할 수 없다 따라서 heapq를 import하여 항상 최소 원소를 빠르게 뱉어낼 수 있도록 선언하자 합체 횟수만큼, heappop을 2번하여 더한 후, 그 결과를 heappush하면 된다 3. 출력하기heap의 sum을 출력해준다 코드(..
링크 : https://www.acmicpc.net/problem/2847 문제소요시간: 8분 25초 설계하기(접근방법) 1. 입력받기레밸의 점수를 입력받는다 2. 구현하기입력받는 점수 리스트를 역으로 순회한다 i 레밸이 i-1 레밸보다 큰 경우 continueelse 인 경우에는 (둘의 차이 + 1)만큼 cnt 에 더해주고, i-1 레밸을 i레벨보다 1작게 선언해준다 3. 출력하기cnt를 출력한다 코드(출력)import sysinput = sys.stdin.readlinen = int(input())cnt = 0level = []for _ in range(n): point = int(input()) level.append(point)for i in range(n - 1, 0, -1): ..
링크 : https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 소요시간: 30분 설계하기(접근방법) 1. 입력받기 구멍의 개수와 테이프의 길이를 입력받는다 2. 구현하기 테이프를 잘라서 사용할 수 없으니 중간부터 붙여서 이득을 보는 경우는 없다. 그리디하게 앞에서부터 일단 붙여나가야 한다 리스트를 정렬해주고 테이프를 앞에서부터 붙인다 첫번 째 구멍부터 테이프를 붙인다 그러면 테이프 끝의 위치는 구멍 + 테이프의 길이가 될 것이다..
링크 : https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 소요시간: 25분 실패 설계하기(접근방법) 1. 입력받기 2. 구현하기 1. 세트 1개가 낱개 1개보다 싼 경우 or 일정 범위부터 나머지 낱개 대신 세트로 사는게 저렴한 경우 -> 모두 세트로 구하기 2. 세트 1개가 낱개 6개보다 비싼 경우 -> 세트를 사지 않는다 -> 모두 낱개로 구하기 3.세트 랑 낱개를 섞어서 사는 경우 -> 섞어서 구한다 3. 출력하기 3 가지 중에 ..
링크 : https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 소요시간: 47분 10초 설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기 먼저 1차원 배열을 left를 기준으로 정렬한다 그 후 케이스를 나누어서 더해나가야 한다 이전 left, right 현재 n_left, n_right 케이스 1) 1 4 2 5 인 경우 이전의 for문에서 4 -1만큼 cnt에 더해주고 이전 right인 4를 넘..
링크 : https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 소요시간: 55분 설계하기(접근방법) 1. 입력받기 등수를 입력받는다 2. 구현하기 먼저 현재 등수에 자리 배치가 가능한 사람은 모두 배치한다 그 후 작은 등수를 순서대로 앞에서부터 빈자리를 가득 채운다 3. 출력하기 빈자리에 강제로 앉은 사람의 불만도의 합을 출력한다 코드(출력) import heapq n = int(input()) maybe_rank = [] real_rank = [0 ..
링크 : https://www.acmicpc.net/problem/1459 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 문제 소요시간: 38분 21초 설계하기(접근방법) 1. 입력받기 목표 좌표, 이동 가중치를 입력받는다 2. 구현하기 처음에 while문으로 돌려서 시간초과가 났다 사실 좌표값 만큼 빼는 것이기 때문에 굳이 while문을 안돌리고 몫만 구해서 빼도 되는 것이었다 먼저 x,y 중 하나가 0이 될때까지 만들고, 둘 다 짝수로 만든다 -> 그래서 평행선에서 대각선 이동으로 목적지에 도달할 수 ..
링크 : https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 소요시간: 40분 실패 설계하기(접근방법) 1. 입력받기 조건대로 입력받는다 2. 구현하기 처음에는 구현을 해버렸다 지금 숫자와 다음 숫자를 비교해서 다음 숫자가 크면 다음 숫자로 바꿔주고 지금 숫자가 크다면 앞에서 부터 1자리씩 줄여가면서 크기를 비교하고 다음 숫자가 큰 경우가 생기면 그 부분만 떼서 교체해준다 예를 들어 10 4 4177252841 일때 1 : 417725 2 : 417725 > 177252 3 : 417725 < 772528 4 : 772..
