[200318/D-5] 백준 알고리즘 공부

푼 문제 :  11726, 11727, 9095

전체 비율 :  / 155 (약 %) 

공부 시간 :

 

11726

Bottom-up 

import java.io.IOException;
import java.util.Scanner;

public class Main{
        
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int[n+1];
        
        dp[0] = 1; 
        dp[1] = 1;
        
        for(int i = 2; i <= n; i++) {
        	dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        
        System.out.println(dp[n]);
        
    }


}

진짜 충격적으로 머리 안 돌아간다.

일단 10007 사용하는 이유는 10000보다 큰 최초의 소수라서 사용. 사용하지 않으면 런타임 에러 날 수 있음. 

 

9095

import java.io.IOException;
import java.util.Scanner;

public class Main{
	    
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[11];
        
        dp[0] = 1;
        dp[1] = 1; 
        dp[2] = 2;
        dp[3] = 4;
        
        for(int i = 4; i < 11; i++) {
        	dp[i] = dp[i-3] + dp[i-2] + dp[i-1]; 
        }
        
        System.out.println(dp[n]);
        
    }

}

계속 틀렸다고 하는데 이유를 모르겠다. 일단 결과 값은 제대로 나옴. 

(답답해서 죽어버림)

top-down으로 풀어봤다.

import java.io.IOException;
import java.util.Scanner;

public class Main{
	
	public static int[] dp; 
	
	public static int cal(int n) {
		if(n == 0 || n == 1) {
			dp[n] = 1;
			return 1;
		}
		
		if(n == 2) {
			dp[n] = 2;
			return 2;
		}
		
		if(dp[n] > 0) {
			return dp[n]; 
		}
		
		dp[n] = cal(n-3) + cal(n-2) + cal(n-1); 
		return dp[n]; 
	}
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dp = new int[n+1]; 
        System.out.println(cal(n));
        
    }

}

실패 (오열)

일단 top-down은 제한 조건 때문이려나

화가 나니 일단 패스한다.

 

 

 

한 문제, 한 문제가 조금씩 오래 걸려서 조급해지는데 진정하자.