[Java] 백준 - 1904번: 01타일

5월 4일(목) - 동적 계획법 1 (1904번)

1904번: 01타일

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전
	int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];


// 수정 후
	int N = Integer.parseInt(br.readLine());
        int[] dp = new int[1000001];

1. dp 배열의 크기를 N+1로 설정했더니 런타임 에러(ArrayindexOutOfBounds) 가 발생

-> dp 배열의 크기를 1,000,001으로 설정했더니 통과

-> 아래 링크의 글의 댓글을 통해서 원인 파악

[백준] 1904번 : 01타일 - JAVA [자바]

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(C언어 풀이 활용)

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

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());
        int[] dp = new int[1000001];

        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=N; i++)
        {
            dp[i] = (dp[i-2] + dp[i-1]) % 15746;
        }

        System.out.println(dp[N]);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(풀이출처 -> https://st-lab.tistory.com/125)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static int[] dp = new int[1000001];;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		int N = Integer.parseInt(br.readLine());
			
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
 
		for(int i = 3; i < dp.length; i++)
        {
			dp[i] = -1;
		}
		
		System.out.println(Tile(N));
	}
	
	public static int Tile(int N) {
		if(dp[N] == -1)
        {
			dp[N] = (Tile(N - 1) + Tile((N - 2))) % 15746;
		}
		return dp[N];
	}
 
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ