DHistory

문제https://www.acmicpc.net/problem/2304 풀이오목하게 들어간 부분이 없으려면, 루프탑 기준 왼쪽과 오른쪽으로 나누어 문제 풀이를 진행해야 합니다.오른쪽 부분은 순서를 뒤집어서 문제를 풀어야 루프탑과 연결했을 때 오목한 부분이 없습니다. 루프탑 기준으로 왼쪽 부분과 오른쪽 부분으로 나눈 후 왼쪽 부분의 합 + 오른쪽 부분의 합 + 루프탑 사이의 합을 구하면 됩니다. 예시72 411 415 84 65 38 1013 6 왼쪽 배열: (2, 4) (4, 6) (5, 3) (8, 10)오른쪽 배열: (8,10) (11, 4) (13, 6) (15, 8)→ 루프탑: (8, 10) 왼쪽 배열의 합: (4 - 2) * 2 + (5 - 4) * 6 + (8 - 5) * 6오른쪽 배열의 합: ..

문제https://www.acmicpc.net/problem/24444 풀이그래프 탐색 이용1. 정점 번호 오름차순 정렬2. BFS를 이용한 풀이3. 정점 방문 전 숫자 1 증가 예시5 5 11 41 22 32 43 4  코드import sysfrom collections import dequen, m, r = map(int, sys.stdin.readline().rstrip().split())edges = [[] for _ in range(n + 1)]visited = [0] * (n + 1)for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split()) edges[x].append(y) edges[y].append(x..

문제https://www.acmicpc.net/problem/24479 풀이그래프 탐색 이용1. 정점 번호 오름차순 정렬2. DFS 를 이용한 풀이3. python 함수 호출 수 제한 변경 예시5 5 11 41 22 32 43 4   코드import syssys.setrecursionlimit(130000)n, m, r = map(int, sys.stdin.readline().rstrip().split())edges = [[] for _ in range(n + 1)]visited = [0] * (n + 1)for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split()) edges[x].append(y) edges[y].a..

문제https://www.acmicpc.net/problem/5567 풀이그래프 탐색 이용1. BFS 활용2. 방문하지 않았으면 방문 (기존 방문 + 1)3. 인접 정점 할당 예시651 21 33 42 34 5  코드import sysfrom collections import dequen = int(sys.stdin.readline().rstrip())m = int(sys.stdin.readline().rstrip())edges = [[] for _ in range(n + 1)]visited = [0] * (n + 1)for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split()) edges[x].append(y) edg..

문제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..