nose딩

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);
    }
}

타일링 문제랑 비슷한 늒힘

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[][] dp= new int[41][2];
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	dp[0][0]=1; //숫자, 0의 개수
    	dp[0][1]=0; //숫자, 1의 개수
    		
    	dp[1][0]=0;
    	dp[1][1]=1;
    		
    	for(int i=2; i<=40; i++) {
    		dp[i][0]=dp[i-1][0]+dp[i-2][0];
    		dp[i][1]=dp[i-1][1]+dp[i-2][1];
    	}
    	
       	int n = Integer.parseInt(br.readLine());
    	
    	for(int i=0; i<n; i++) {
    		int num = Integer.parseInt(br.readLine());
    		bw.write(dp[num][0]+" "+dp[num][1]+"\n");
    	}
    	bw.flush();
    	bw.close();
    }
}

n범위가 정해져있어서 피보나치 미리 만들어준 후에 했다

이차원 배열을 사용하여 0의 개수 1의 개수를 더해나가기 예엥~

class Solution
{
    static int[][] dp;
    public int solution(int [][]board)
    {
        dp = new int[board.length+1][board[0].length+1];
        int max = 0;
        
        for(int i = 1; i<=board.length; i++){
            for(int j=1; j<=board[0].length; j++){
                dp[i][j]=board[i-1][j-1];
            }
        }
        
        for(int i = 1; i<=board.length; i++){
            for(int j=1; j<=board[0].length; j++){
                if(dp[i][j]==1){
                    dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
                    max = Math.max(dp[i][j],max);
                }
            }
        }
        return max*max;
    }
}

왼쪽, 바로위, 왼쪽바로위 이렇게 세 값 중 최소값에 1을 더한걸 현재 dp에 저장하며 갱신~

,,다들 천잰가 ,, 나도 점화식 스스로 떠올리고 싶다구요 ,,

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> st = new Stack<Character>();
        for(int i = 0; i<s.length(); i++){
            if(s.charAt(i)=='('){
                st.push('(');
            }else{
                if(st.isEmpty()){
                    return false;
                }
                st.pop();
            }
        }
        if(!st.isEmpty()) answer = false;
        return answer;
    }
}

괄호하면 스택이쥬~ 이것은 국룰~