백준 [자바 java] 1495번 : 기타리스트

 분명 처음 봤을 때에는 dp라고 생각했지만 막상 어떻게 풀어야 할지 생각이 나지 않아서 스택 두 개로 주고받고 하는 형식으로 풀었었다. 하지만 가차 없이 메모리 초과가 났다. 예전에 한번 풀어봤던 것 같아서 이제까지 풀었던 dp문제를 다시 쭉 봤다.

 그 중 안녕이라는 문제와 제일 비슷했다. dp는 최댓값을 저장하고 나머지를 버린다라는 고정관념이 있었는데 이 dp는 한계 수가 있으면 그만큼 수열을 만들어주고 해당하는지 아닌지 표시하는 방식이다. 

import java.util.*;
import java.io.*;


class Main{
	
 public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    
   
    
    st = new StringTokenizer(br.readLine());
    int i;
    int[][] arr = new int[a+1][c+1];
    int[] aa = new int[a];
    for( i =0;i<a;i++) {
    	aa[i] = Integer.parseInt(st.nextToken());
    }
    int j;
    int k;
    int ok = 0;

			if(b-aa[0] >=0) {
				ok = 1;
				arr[1][b-aa[0]] = 1;
			}
			if(b+aa[0] <= c) {
				ok = 1;
				arr[1][b+aa[0]] = 1;
			}
		
	
    
    for( i =2;i<=a;i++) {
    	ok = 0;
    	for(j = 0;j<=c;j++) {
    		if(arr[i-1][j] == 1) {
    			
    			if(j-aa[i-1] >=0) {ok = 1;
    				arr[i][j-aa[i-1]] = 1;
    			}
    			if(j+aa[i-1] <= c) {ok = 1;
    				arr[i][j+aa[i-1]] = 1;
    			}
    		}
    	}
    	if(ok == 0) {
    		
    		break;
    	
    	}
    	
    }
    
    int max = 0;
    
    if(ok == 0) {
    	System.out.println(-1);
    	
    }
    else {
    for(j = 0;j<=c;j++) {
    	if(arr[a][j] ==1) {
		max = j;}
	}
    
    System.out.println(max);}
    
 }
 
 
 }

이차원 배열[곡 수][한계치]를 만들고 해당하는 것에 1을 넣어주었다. 그리고 마지막에 가장 큰 j를 넣어주었다. 이 문제는 거의 다 와서 삽질을 많이 했다. 우선 ok값을 위칸 기준으로 했는데(위칸이 다 비었나) 곡 수가 한 개면 성립하지 않았다. 그리고 aa는 0부터 시작인데 arr은 1부터 시작이라 헷갈린 부분도 있었다. 

알아야 할 점

 반례를 찾을 때에는 할 수 있는 가장 작은 수를 넣어보자

 모든 경우의 수를 고려해봐야 하는 dp문제는 가능한 모든 수의 수열을 만들고 표시해나가는 방식으로 풀자

 

다른사람 코드와 다른 점 : 딱히 없다.(예시가 많이 없었다)