2025/07

https://www.acmicpc.net/problem/1102풀이발전소가 N개 있고, 어떤 발전소는 작동 중(y), 어떤건 꺼져 있다. (N)작동 중인 발전소가 다른 발전소를 켜는 데 드는 비용이 주어진다. (A[i][j])발전소를 P개 이상 켜기 위해 최소 비용을 구하는 문제이다.켜는 순서와 조합에 따라 총 비용이 달라진다.즉 최적의 순서를 구해야한다.주요 알고리즘은 비트마스킹 + 메모이제이션을 사용한다.입력 처리는 다음과 같이 비교적 간단하게 입력 받는다.N = int(input())A = [list(map(int, input().split())) for _ in range(N)]S = input()P = int(input())캐시 초기화를 위해서 65536개의 캐시를 생성한다.cache = [-..

https://www.acmicpc.net/problem/1354풀이A(0) = 1 A(n) = A(n // P - X) + A(n // Q - Y) (n > 0)주어진 N에 대해서 A(N)을 구하는 문제이다.기본 수열 정의A(n)은 자기보다 작은 인덱스들의 결과를 이용해 계산됨 → 전형적인 DP 구조문제점N이 최대 10^12이기 때문에 일반적인 리스트 기반 DP(dp = [0]*(N+1))는 메모리 초과 → 딕셔너리 기반 메모이제이션 사용점화식 재귀 정의점화식에 따라 다음과 같이 재귀함수 작성A(n) = A(n // P - X) + A(n // Q - Y)기저 조건n 메모이제이션계산된 결과는 cache[n]에 저장해서 중복 호출 방지def dp(n): if n 재귀 함수를 정의한다.시간복잡도..