7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 분석 유사문제 : 2631 [2631] 줄 세우기 (2중 for문) 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과 karla.tistory.com 추가 조건 : 이동하는 어린이를 제일 앞이나 제일 뒤로만 보낼 수 있음 ➔ 바로 옆에 있는 최장 증가 수열을 구해야함 4 2 3 1 5 1. 한 명의 어린이를 뽑아서 원하는 곳..

2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys from bisect import bisect_left input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) d=[] for i in arr: k = bisect_left(d, i) if len(d) == k: d+=[i] else: d[k]=i ..

2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) dp = [0 for _ in range(n)] for i in range(n): dp[i] = 1 for j in range(i): if arr[j] < arr[i]: dp[i] = max(d..

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