DHistory

문제https://www.acmicpc.net/problem/1965 풀이큰 문제를 작은 문제로 풀 수 있는 DPd[n]: n 번째 상자일 때, 한 번에 넣을 수 있는 최대의 상자 개수 예시1) 기준 상자일 때,2) 기준 상자보다 왼쪽에 있는 상자들 중 최대 상자 개수 구하기3) 본인 상자 추가 코드import sysn = int(sys.stdin.readline().rstrip())boxes = list(map(int, sys.stdin.readline().rstrip().split()))d = [1] * 1000for i in range(n): for j in range(i): if boxes[i] > boxes[j]: d[i] = max(d[i], d[j] + ..

문제https://www.acmicpc.net/problem/2075  풀이우선 순위 큐 사용1) 주어진 숫자를 구하고자하는 길이 만큼 넣는다.2) 제일 작은 수보다 큰 숫자가 주어진 경우 제일 작은 수를 제외하고 큰 숫자를 넣는다. 예시127915513811196211026311648142835255220324149 첫번째 줄5, 7, 9, 12, 15 두번째 줄13인 경우: 5, 7, 9, 12, 15 → 5제외 13추가 → 7, 9, 12, 13, 158인 경우: 7, 9, 12, 13, 15 → 7제외 8추가 → 8, 9, 12, 13, 1511인 경우: 8, 9, 12, 13, 15 → 8제외 11추가 → 9, 11, 12, 13, 1519인 경우: 9, 11, 12, 13, 15 → 9제외 1..

문제https://www.acmicpc.net/problem/11048 풀이큰 문제를 작은 문제로 나누어 풀 수 있는 DP 문제이다. D[N][M]: (N, M) 위치에 있을 때, 사탕을 최대한 많이 가져올 수 있는 개수 1. 첫 블럭 예외 (첫 블럭이 곧 사탕 최대 개수)2. i 열이 0인 경우 첫 블럭부터 계속 쌓아온 사탕 개수3. j 열이 0인 경우 첫 블럭부터 계속 쌓아온 사탕 개수4. 대각선인 경우 아래 경우의 수 중 가장 큰 사탕 개수  4-1) 위에서 온 경우  4-2) 왼쪽에서 온 경우  4-3) 대각선에서 온 경우예시3 x 4사탕 수123400059876 최대 개수136101361510182531 코드import sysn, m = map(int, sys.stdin.readline().rs..

문제https://www.acmicpc.net/problem/9184 풀이재귀함수 호출 결과를 미리 저장한다. (팩토리얼 문제와 유사)함수를 호출하는 부분을 미리 저장한 내용을 불러오면 된다. 코드import sysnumber = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]def w(a, b, c): if a 20 or b > 20 or c > 20: return number[20][20][20] if a

문제https://www.acmicpc.net/problem/16953 풀이A를 B로 바꾸는 조건1. 2를 곱한다.2. 1을 수의 가장 오른쪽에 추가한다. A(작은 수)를 B(큰 수)로 변경하려면 많은 고려사항이 필요하다. (2를 곱해보고 1을 추가하고, 2를 여러번 곱하고 1을 추가하고 등)반대로 생각하여 B를 A로 변경할 수 있는지 확인하면 된다. 1. 2를 나눈다.2. 1을 수의 가장 오른쪽에거 제거한다.3. 1을 제외한 홀수인 경우 만들 수 없다. 예시1) 2, 162 가 주어진 경우 162: 짝수이므로 2로 나눈다.81: 1을 가지므로 오른쪽에서 제거한다.8: 짝수이므로 2로 나눈다.4: 짝수이므로 2로 나눈다.2: A와 동일하므로 종료한다. 2) 4, 42 가 주어진 경우42: 짝수이므로 2로..

문제https://www.acmicpc.net/problem/18870 풀이좌표 압축이란?Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수 1. 서로 다른 좌표이기 때문에 중복된 숫자 제거2. 오름차순 정렬 시 index == 좌표 압축 결과3. index 정보를 활용하여 입력 숫자에 맞는 좌표 압축 결과 출력 예시1) 2, 4, -10, 4, -9가 주어진 경우중복 숫자 제거: 2, 4, -10, -9오름차순 정렬: -10(0), -9(1), 2(2), 4(3) 2) 1000, 999, 1000, 999, 1000, 999가 주어진 경우중복 숫자 제거: 1000, 999오름차순 정렬: 999(0), 1000(1) 코드import sysfrom collections import dequen = int..

문제 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) p = list(map(int, sys.stdin.readline().rstrip().split()))[:n] m = int(sys.stdin.readline().rstrip()) d = [0] * (m + 1) # 큰 값을 구해야하므로, 큰 값부터 넣는다. for i in range(n - 1, -1, -1): # 숫자의 가격부터 의미가 있으므로 p[i]로 설정한다. for j in range(p[i], m + 1): # 현재 숫자의..

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 1. root node는 여러 개일 수 있다. 2. 제거할 node는 연결 그래프를 만들지 않는다. 3. 제거할 node이거나 이미 방문한 경우라면 탐색을 종료한다. 4. Leaf Node인 경우 탐색을 종료하고 Count한다. import sys n = int(sys.stdin.readline().rstrip()) nodes = [[] for _ in range(n)] parent = list(map(int, sys.stdin.readline(..

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 진실을 아는 인원가 같은 집합에 속한 경우 진실을 아는 경우로 생각한다. 서로소 집합(disjoint sets)을 활용하여 진실을 아는 집합을 구한다. import sys import itertools n, m = map(int, sys.stdin.readline().rstrip().split()) knows = list(map(int, sys.stdin.readline().rstrip().split()))[1:] parties = [] parent = [i f..

문제 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이 같은 색이 지정된 면은 평행하기 때문에 어느 한 면을 선택한다면, 다른 면은 선택할 수 없다. N^3개의 주사위로 정육면체를 만든다면 주사위의 면을 1개만 사용하는 경우, 주사위의 면을 2개만 사용하는 경우, 주사위의 면을 3개만 사용하는 경우가 있다. N x N(N은 2이상)으로 정육면체를 만들었을 경우 아래 사진처럼 정육면체를 만들 수 있다. 노란색 부분: 주사위의 면을 1개 사용하는 경우 (최상층을 제외하고 한 면을 기준으..