DHistory

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