[200324/D-8] 백준 알고리즘 공부

푼 문제 :  

전체 비율 :  / 155 (약 %) 

공부 시간 : 약 2시간

 

11057

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

public class Main{
	
	public static long dp[][];
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new long[n+1][10];
        long sum = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 10; j++) {
            	if(i == 1) {
            		dp[i][j] = 1;
            	}else{
            		if(i == 2) {
            			dp[i][j] += j;
        			}else {
                		for(int k = 0; k <= j; k++) {
                    		dp[i][j] += dp[i-1][k];
                			dp[i][j] = dp[i][j] % 10007;
                		}        				
        			}

            	}
            	
        		sum += dp[i][j];
            }
       }
        
        System.out.println(sum % 10007);
        
    }
   
}

다른 사람들 코드가 이해가 안 간다.

그렇다고 내 코드가 마음에 드는건 절대 아니라 혼란스럽다. 

그 와중에 코드블럭 정렬 무슨 일이야?

 

일단 다른 분들 코드 보면서 생각해 봐야겠다. 왠만하면 같은 횟수로 반복 되는 경우에는 그 안에서 해결하려고 하는게 별로 안 좋은 습관 같은 걸까? 다들 for문이 단독으로 여러개인데 나만 이상하게 if-else문에 for문 넣어놓고 있다. 

 

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

public class Main{
	
	public static long dp[][];
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new long[n+1][10];
        long sum = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 10; j++) {
            	if(i == 1) {
            		dp[i][j] = 1;
            	}else{
                		for(int k = 0; k <= j; k++) {
                    		dp[i][j] += dp[i-1][k];
                			dp[i][j] = dp[i][j] % 10007;
                		}        				
                		
            	}
            	
            }
       }
     
        for(int i = 0; i < 10; i++) {
        	sum += dp[n][i];
        }
        System.out.println(sum % 10007);
        
    }
   
}

일단 조금 더 마음에 드는 코드는 이거

 

2193

 

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

public class Main{
	
	
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n >= 91) {
        	return; 
        }
        int dp[] = new int[n+1];
        dp[1] = 1;
        dp[2] = 1;
        
        for(int i = 3; i <= n; i ++) {
        	dp[i] = dp[i-1] + dp[i-2];
        }
        
        System.out.println(dp[n]);        
        
    }
   
}

규칙을 찾았고 2차원 배열로 하려고 했는데 아니 피보나치처럼 답이 나오는거 아닌가. 엥 이렇게 쉽다고? 하면서 제출했으나 역시나 틀렸습니다.

 

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

public class Main{
	
	
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        
        long dp[][] = new long[n+1][2];
        dp[1][0] = 0;
        dp[1][1] = 1;
        
        for(int i = 2; i <= n; i ++) {
        	dp[i][0] = dp[i-1][0] + dp[i-1][1];
        	dp[i][1] = dp[i-1][0];
        }
        
        System.out.println(dp[n][0] + dp[n][1]);        
        
    }
   
}

 

그래도 조금 감을 익혀가는 것 같아서 다행이다. 

일단 점화식 찾는 감은 조금 생긴거 같은데 역시나 dp 배열로 구현하는게 어렵다.

 

+

티스토리 임시저장 기능 진짜 불편하다. 

자동으로 저장되는거 같기는 한데 이미 날린 것만 해도 몇 개 있음. 어이없네. 나중에 가면 이런 형식이 더 편 할 수도 있겠지 뭐