nose딩

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

public class main {
	static long[][] dp;
	static int N;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	N = Integer.parseInt(br.readLine());
    	
    	dp = new long [N+1][10]; //N: 자리수
    	
    	for(int i=1; i<10; i++) {
    		dp[1][i] = 1L;
    	}
    	for(int i=2; i<=N; i++) {
    		dp[i][0] = dp[i-1][1];
    		for(int j=1; j<9; j++) {
    			dp[i][j]= (dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
    		}
    		dp[i][9] = dp[i-1][8];
    	}
    	long answer=0;
    	for(int i=0; i<=9; i++) {
    		answer+=dp[N][i]%1000000000;
    	}
    	bw.write(answer%1000000000+"\n");
    	bw.flush();
    	bw.close();
    }
}

너무 dp 문젠데 알아채지 못했다.. 진짜 많이 풀어봐야겠다 양치기 가겠슴돠~

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
public class main {
	static int N;
    static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
       	N = Integer.parseInt(br.readLine());
       	dp(N,0);
       	
   		bw.write(answer+" ");
    	bw.flush();
    	bw.close();
    }
	static void dp(int n, int count) {
		if(n==1) {
			answer = Math.min(answer,count);
			return;
		}
		if(count >= answer) return;
		
		if(n%3==0) {
			dp(n/3,count+1);
		}
		if(n%2==0) {
			dp(n/2,count+1);
		}
		dp(n-1,count+1);
	}
}

제일 먼저 떠오른게 함수만들어서 재귀로 count 1씩 증가시키면서 넘겨주는 거 였는데

오래걸릴 거라고 생각했다 힝

count가 answer 보다 크면 return 하는 이유는 

count의 최대의 경우는 n-1 이기 때문 ~ 즉,,하나도 나누지 않고 1씩 다빼주는 경우

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[][] dp;
	static int N;
    static StringTokenizer st;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
       	N = Integer.parseInt(br.readLine());
       	dp = new int[N+1][3]; //1, 2 : 전에 칸 개수 
       	
       	for(int i =1; i<=N; i++) {
       		dp[i][1] = Integer.parseInt(br.readLine());
       		dp[i][2]=dp[i][1];
       	}
       	
       	if(N==1) {
       		bw.write(dp[N][1]+" ");
        	bw.flush();
        	bw.close();
        	return;
       	}else if(N==2) {
       		bw.write((dp[1][1]+dp[N][1])+" ");
        	bw.flush();
        	bw.close();
       		return;
       	}
       	
       	dp[1][2]=0;
       	dp[2][1]+=dp[1][1];
       			
       	for(int i =3; i<N; i++) {
       		dp[i][1] += dp[i-1][2];
       	    dp[i][2] += Math.max(dp[i-2][1],dp[i-2][2]);
       	}
       	
   		bw.write(Math.max(dp[N-1][2],Math.max(dp[N-2][1],dp[N-2][2])) + dp[N][1]+" ");
    	bw.flush();
    	bw.close();
    }
}

예외처리가 살짝 지저분해 보이네 ㅎ ,,

풀고 나서 사람들 풀이 봤는데 아예 점수 배열을 따로,, 만들더라구요?

난,, 이차원 배열로 dp배열을 만들었다.. ㅎ

[1]에는 바로 직전에서 온 애들 [2]에는 전 전에서 온애들을 저장했다.

그래서 바로 전에서 온애는 연달아가 안되니까 [2]애들을 더해주고,

전전에서 온애는 다 올 수 있으니 [1],[2] 중에 큰 값 더해준다.

전 전에서서는 그 전에 한칸 올랐는지 두칸올랐는지 상관없으니 다 갈 수있으니깐~

그 식이

dp[i][1] += dp[i-1][2]

dp[i][2] += Math.max(dp[i-2][1], dp[i-2][2]

예엥~

새로 푼거

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class main {

	static int dp[];
	static int arr[];
	static int N;

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

예엥

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[][] dp;
	static int N;
    static StringTokenizer st;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
       	N = Integer.parseInt(br.readLine());
       	dp = new int[N][N];
       	
       	for(int i =1; i<=N; i++) {
       		st = new StringTokenizer(br.readLine()," ");
       		if(N==1) {
    			bw.write(st.nextToken()+"\n");
    			bw.flush();
    			bw.close();
    			return;
    		}
       		for(int j=0; j<i; j++) {
       			dp[i-1][j]=Integer.parseInt(st.nextToken());
       		}
       	}
       	
       	dp[1][0]+=dp[0][0];
       	dp[1][1]+=dp[0][0];
       	
       	for(int i =2; i<N; i++) {
       		
       		dp[i][0]+=dp[i-1][0];
       		for(int j=1; j<i; j++) {
       			dp[i][j]+=Math.max(dp[i-1][j-1],dp[i-1][j]);
       		}
       		dp[i][i] += dp[i-1][i-1];
       	}
       	
       	int max = 0;
       	for(int i=0;i<N; i++) {
       		if(dp[N-1][i]>=max) max = dp[N-1][i];
       	}
       	
   		bw.write(max+" ");
    	bw.flush();
    	bw.close();
    }
}

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이 에제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

-> 이 말은 곧, 밑에 있는 수에 위에서 왼쪽위랑 오른쪽위중에 큰 값을 더해나가면 된다는 뜻 ~~~~

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

전에 풀었던 문제랑 비슷한 문제 ,, 예엥

앞에꺼에 바로 위 제외한 값에서 최소 더해나가기 ~

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static long[] dp;
    static StringTokenizer st;
	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());
       	
     	dp = new long[101];
     	dp[1]=1;
     	dp[2]=1;
     	dp[3]=1;
     	dp[4]=2;
     	dp[5]=2;
     	for(int i =6; i<101; i++) {
     		dp[i]=dp[i-1]+dp[i-5];
     	}
     	
       	for(int i =0; i<n; i++) {
       		int num = Integer.parseInt(br.readLine());
       		
       	   	bw.write(dp[num]+"\n");
       	}
    	bw.flush();
    	bw.close();
    }
	
	
	
}

아니 점화식은 진작에 구했는데,,

Long 처리 해주어야 하는지 몰랐다.

어쩐지 얜 답 나누라고 안하더라 , , , , , 롱 ,,,,,,,,,,,, 하 항ㅎ

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[] dp;
    static StringTokenizer st;
	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());
       	
       	dp = new int[1000001];
       	
       	bw.write(w(n)+"\n");
       		
    	bw.flush();
    	bw.close();
    }
    
    static int w(int n) {
    	if(n==1) return 1;
    	if(n==2) return 2;
    	if(dp[n]!=0) return dp[n];
    	return dp[n]=(w(n-2)+w(n-1))%15746;
    }
}

역시 써보는게 최고,, 베이비 문제네,,

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[][][] dp;
    static StringTokenizer st;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       	while(true) {
       		dp= new int[21][21][21];
       		st = new StringTokenizer(br.readLine()," ");
       		int a = Integer.parseInt(st.nextToken());
       		int b = Integer.parseInt(st.nextToken());
       		int c = Integer.parseInt(st.nextToken());
       		if(a==-1 && b==-1 && c==-1) break;
       		bw.write("w("+a+", "+b+", "+c+") = "+w(a,b,c)+"\n");
       	}
    	bw.flush();
    	bw.close();
    }
    
    static int w(int a, int b, int c) {
    	if(a<=0 || b <=0 || c<=0) return 1;
    	if(a>20 || b>20 || c>20) return w(20,20,20);
    	if(dp[a][b][c]!=0) return dp[a][b][c];
    	if(a<b && b<c) return dp[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    	return dp[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
}

타일링 문제랑 비슷한 늒힘