풀이

DP배열을 생성해, Bottom Up방식으로 풀이.

dp[0]=1이 왜 1인가에 대해 고민을 좀 많이 했던 문제였다.

문자열의 길이가 0인게 없지않나?? 라는 생각을 많이했다.

1. 문자열의 길이가 0인 경우가 ""의 경우가 존재할 수도 있겠구나라는 생각

2. dp[0]을 1로 설정해주지 않으면 문제 풀이자체가 되지않겠구나. dp[i]=0일테니까.

고민을해서 위와 같은 결론을 내렸다.

위의 그림은, 해당 문제의 Solution 탭의 그림의 일부인데.

문제에서 말하는 좋은 문자열이 되기 위해서는

1. 마지막에 해당 숫자만큼 붙였을때 알맞은 길이의 숫자가 되는것

2. 그러기 위해서는 i가 zero, one보다 크거나 같을때 : 해당 dp[i]가 ++될 것이다.

까지 생각을 할 수 있었다.

이게 무슨말인고? 하니

위의 그림에서 자세하게 idx = 5까지가는 과정을 살펴보자.

모든 dp[idx]배열의 값에, 들어갈 수 있는 경우의 수는

dp[idx-zero]나, dp[idx-one] 두 경우에서 만족하는 경우의 배열들을 추가해준 값이 해당 dp[idx]에 들어갈 수 있는 총 문자열의 개수가 될 수밖에 없다.

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
    	int answer = 0;    	    	
    	int[] dp = new int[high+1];
    	dp[0] = 1;

    	for(int i=1; i<=high; ++i) {
    		if(i>=zero) dp[i] += dp[i-zero];
    		if(i>=one) dp[i] += dp[i-one];
    		
    		dp[i] %= 1_000_000_007;
    	}
    	
    	for(int i=low; i<=high; i++) {
    		answer += dp[i];
    		answer %= 1_000_000_007;
    	}
    	
        return answer;
    }
}

O(n) (n=high)의 시간복잡도를 가지는 코드가 완성됐다.

풀이

DFS를 이용해서, 해당 칸을 탐색할 수 있을 경우 탐색해서 모든 경우의수를 구한다음 최대값을 구하는 단순 DFS문제라고 생각했다.

class Solution {
	public static long max = -1;
	
    public long mostPoints(int[][] questions) {
       	if(questions.length==1) return questions[0][0];

        boolean[] bl = new boolean[questions.length];
        
        for(int i=0; i<questions.length; i++) {
        	dfs(questions[i][0], i, questions[i][1]+1, questions, bl);
        }        
    	return max;
    }
    
    public void dfs(long sum, int idx, int tmp, int[][] questions, boolean[] bl) {
    	if(idx >= questions.length) {
    		max = Math.max(max, sum);
    		return;
    	}    	
    	
    	for(int i=idx; i<questions.length; i++) {    		    		
    		if(tmp != 0) {
    			tmp--;
    			continue;
    		}
    		if(bl[i]) return;
    		bl[i]=true;
    		dfs(sum+questions[i][0], i+1, tmp+questions[i][1]+1, questions, bl);
    		bl[i]=false;
    	}
		max = Math.max(max, sum);
    }
}

분명 IDE의 콘솔에서는 정답이 출력되는데 왜 틀렸다고 하는지 모르겠다. 나는 100이 나오는데 ㅡㅡ

머리 환기시키고 재도전해봐야겠다..