Total

[11053] 가장 긴 증가하는 부분수열 (LIS)

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 분석 1 ≤ N ≤ 1,000 1 ≤ Ai ≤ 1,000 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dp = [1]*n for i in range(1,n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i],..

[8980] 택배

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 분석 N ≤ 100, M ≤ 1,000, C ≤ 2,000 도착 지점(받는 마을)이 먼저인 순으로 정렬 풀이 """ 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다. 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다. 조건 3: 박스들 중 일부만 배송할 수도 있다. 마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그..

[1700] 멀티탭 스케줄링 (플러그 교체 최소 횟수)

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 분석 사용 순서대로 진행 이미 꽂은 경우 넘김 플러그 자리 체크 꽃을 수 있는 경우 플러그에 append 꽉찬 경우 앞으로 꽂을 거 중에 가장 대기 멀리 있는거 찾아서 뽑고 cnt +1하고 현재 플러그 append cnt 출력 풀이 """ 3구 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 1. 키보드 2. 헤어드라이기 3. 핸드폰 충전기 4. 디지털 카메라 충전기 5. 키보드 6. 헤어드라이기 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를..

[2170] 선 긋기 (선의 총 길이 구하기)

2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 분석 선 배열 정렬 첫번째 선으로 시작 이어져있다면 끝이 더 큰걸로 연결하고, 끊어져있다면 길이 저장 후 새로 시작 풀이 """ 매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자. 이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 ..

[15903] 카드 합체 놀이 (우선순위 큐)

15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 풀이 """ 아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y) 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다. 이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만..

[1439] 뒤집기 (문자열)

1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 """ 0과 1로만 이루어진 문자열 S 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 ..

[2847] 게임을 만든 동준이 (난이도 별 레벨 감소 횟수 구하기)

2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 분석 뒤에서부터 최댓값 설정 최댓값보다 크다면 최댓값보다 1작은 수로 감소하며 횟수 카운트 : cnt+= s[i]-maxScore+1 최댓값 업데이트 풀이 """ 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다..

[11501] 주식 (최대 이익 구하기)

11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 분석 뒤에서부터 현재 주가와 최대 주가 비교 최대주가와 현재 주가의 차이 더하기 (사고 팔 때 가격 차이) 총 합은 최대이익 풀이 """ 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안한다. 예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이..

[2217] 로프 (최대 중량 구하기)

2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 """ k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 2 10 15 """ n=int(input()) w=[] for _ in range(n): w.append(int(input())) w.sort(..

[11000] 강의실 배정

11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 """ 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) 3 1 3 2 4 3 5 """ import heapq import sys input=sys..