-
반응형
https://www.acmicpc.net/problem/1793
풀이
간단한 DP문제입니다.
DP[N] = 2*N의 타일을 배치할 수 있는 경우의 수라고 한다면, 아래의 설명과 같은 논리로 인해 일반식이 완성이 됩니다.
1. 2*N의 타일은 2*(N-1)의 타일에 2*1타일을 세로로 배치하면 되기때문에 DP[N-1]일때의 개의 경우의 수가 생깁니다.
2. 2*N의 타일은 2*(N-2)의 타일에 2*1 타일 두개를 나란히 가로로, 세로로 배치하거나 2*2 타일을 배치하면 되기때문에 DP[N-2] * 3의 경우의 수가 생깁니다.
3. 하지만 여기서 주의해야 할 점은 세로로 두개를 나란히 놓은것과, 2*(N-1)에서 2*1 타일을 하나 배치한것은 겹치기 때문에, 중복되는 경우의수를 빼주어야합니다.
4. 따라서 DP[N] = DP[N-1] + DP[N-2]*2 라는 식이 생기게됩니다.
5. 하지만 LONG값을 충분히 넘어가기때문에, BigInteger 클래스를 사용하여 큰 수 를 처리해줍니다.
시간복잡도
미리 DP를 구해놓고, 입력값에 맞는 DP값을 출력해주면 되고, N값이 최대 250이기때문에, O(1)이 됩니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str; BigInteger[] dp = new BigInteger[250+1]; dp[0] = new BigInteger("1"); dp[1] = new BigInteger("1"); dp[2] = new BigInteger("3"); for (int i = 3; i <= 250; i++) { dp[i] = dp[i - 2].multiply(new BigInteger("2")); dp[i] = dp[i].add(dp[i-1]); } while((str = br.readLine())!=null){ int n = Integer.valueOf(str); System.out.println(dp[n]); } } }
반응형'문제풀이 > 백준oj' 카테고리의 다른 글
[백준OJ] 8980번 택배 (Java) (0) 2022.12.27 [백준OJ] 18232번 텔레포트 경기장 (Java) (0) 2022.12.18 [백준OJ] 1926번 그림 (0) 2022.12.13 [백준OJ] 13022번 늑대와 올바른 단어 (0) 2022.12.06 [백준OJ] 13413번 오셀로 재배치 (0) 2022.12.05 댓글