200924 목 [BOJ] 11054, 1912, 2579

BOJ 11054

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {	

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	br.close();
    	int[] sequence = new int[N+1];
    	int[] dp = new int[N+1];
    	int[] dpReverse = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		sequence[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=1;i<=N;i++) {
    		dp[i] = 1;
    		for(int j=1;j<i;j++) {
    			if(sequence[j]<sequence[i] && dp[i] < dp[j]+1) {
    				dp[i] = dp[j] + 1;
    			}
    		}
    	}
    	for(int i=N;i>=1;i--) {
    		dpReverse[i] = 1;
    		for(int j=i+1;j<=N;j++) {
    			if(sequence[i] > sequence[j] && dpReverse[j]+1 > dpReverse[i]) {
    				dpReverse[i] = dpReverse[j] + 1;
    			}
    		}
    	}
    	int ans = dp[1] + dpReverse[1] -1;
    	for(int i=1;i<=N;i++) {
    		if(ans < dp[i]+dpReverse[i]-1) {
    			ans = dp[i]+dpReverse[i]-1;
    		}
    	}
    	bw.write(String.valueOf(ans));
    	
    	bw.flush();    	
    	bw.close();
    }
}

난 처음에 가장 큰 숫자highestNum을 기점으로해서 어떻게 양쪽으로 구분할 수 있지 않을까 했는데.. 결국 실패했다. 30분정도 고민했다.
구글링을 해보니 가장 일반적인 풀이법은 LIS 풀이법을 앞뒤로 계산해서 값을 구하는 방식이어서 참고해봤다.
DP 문제를 풀면서 내 힘으로 풀어내는 문제가 거의 한 개도 없는 것 같네...ㅋㅋ..

---

BOJ 1912

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {	

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	br.close();
    	int[] sequence = new int[N+1];
    	int[] dp = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		sequence[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	int max;
    	dp[1] = sequence[1];
    	max = sequence[1];
    	for(int i=2;i<=N;i++) {
    		dp[i] = Math.max(dp[i-1]+sequence[i], sequence[i]);
    		max = Math.max(max, dp[i]);
    	}
    	bw.write(String.valueOf(max));
    	
    	
    	bw.flush();    	
    	bw.close();
    }
}

ㅂㄷㅂㄷ 이렇게 간단한 걸... 이번에도 혼자서 못 풀었음..
혼자 나름대로 코드를 짜다보니 이전에 계산된 값을 활용하는 DP스타일이 되었고, 결국 다른 사람 걸 참조하게 되었다.

dp[i] = Math.max(dp[i-1]+sequence[i], sequence[i]);
이미 계산된dp[i-1]에다 sequence[i]값을 더해보고, sequence[i] 랑 비교해서 더 큰 값을 dp[i]에 집어넣으면 되는걸!.
max값은 따로 비교해서 집어넣고..

---

BOJ 2579

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {	

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N = Integer.parseInt(br.readLine());
    	
    	int[] seq = new int[N+1];
    	int[] cache = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		seq[i] = Integer.parseInt(br.readLine());
    	}
    	br.close();
    	
    	cache[1] = seq[1];
    	cache[2] = seq[1] + seq[2];
    	for(int i=3;i<=N;i++) {
    		cache[i] = Math.max(cache[i-3] + seq[i-1] + seq[i], cache[i-2] + seq[i]);
    	}
    	
    	bw.write(String.valueOf(cache[N]));

    	bw.flush();    	
    	bw.close();
    }
}

이건 앞에서 풀었던 와인잔 문제랑 상당히 비슷했다.

자꾸런타임 에러가 떠서 이래저래 해봤는데, 다른 사람들의 코드로 제출해봐도 계속 그러는 걸로 보아 뭔가 다른 문제가 있는 것 같으니, 이쯤하고 pass~