아래는 종만북의 DP의 메모이제이션 코드 패턴이다. //메모이제이션 사용 예 //전부 -1로 초기화 int cache[2500][2500] //a와 b는 각각 [0,2500) 구간 안의 정수 //반환 값은 항상 int형 안에 들어가는 양수 int someObscureFunction(int a, int b) { //기저 사례 처리 if(...) return ...; //답을 구한적이 있으면 곧장 반환 if(cache[a][b] != -1) return cache[a][b]; //답을 구한적이 없으면 여기서 답을 계산 cache[a][b] = ...; return cache[a][b]; } 외발뛰기 코드 import java.util.*; import java.io.*; public class Main { ..
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int testCase = Integer.parseInt(br.readLine()); for(int t=0; t
Brute Force 시 같은 답을 중복으로 세는 상황이 발생할 수 있다 이를 해결하기 위해서는 항상 특정 형태를 갖는 답만을 세는 것이다. 흔히 사용하는 방법으로는 같은 답 중에서 사전 순으로 가장 먼저 오는 답 하나만을 센다. 예를 들어 (1,0),(2,3)이나 (2,3),(0,1)은 세지 않지만 (0,1),(2,3)은 센다. 이렇게 하기 위해서 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아주면 같은 답 중 사전 순으로 먼저 오는 답만을 셀 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedRe..
