-
[BOJ - JAVA] 2502 - 떡 먹는 호랑이(DP) 본문
728x90
반응형
# 주소
https://www.acmicpc.net/problem/2502
2502번: 떡 먹는 호랑이
첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다.
www.acmicpc.net
# 문제

# 문제 해설 및 코드 리뷰
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] dp = new int[n];
for(int i = 1; i <= m/2; i++) {
for(int j = i+1; j < m; j++) {
dp[0] = i;
dp[1] = j;
for(int k = 2; k < n; k++) {
dp[k] = dp[k-1] + dp[k-2];
}
if(dp[n-1] == m) {
System.out.println(dp[0]);
System.out.println(dp[1]);
System.exit(0);
}
}
}
}
}
문제에서 알 수 있듯이 일단 dp의 첫 번째 인덱스와 두 번째 인덱스의 값을 알아내야 합니다.
Scanner로 입력 받으면 시간 초과가 나기 때문에 성능이 가장 좋은 Buffered를 이용해줍니다.
기본적으로 i보다 j가 더 커야하기 때문에 모든 경우의 수에 대비해 i = 1부터, 그리고 j는 i+1부터 dp[n]의 값을 유추해야합니다. 그리고 이 dp의 수열은 피보나치수열이기 때문에 정해지는 dp[0]과 dp[1]의 값에 따라 dp[n]의 값은 상이할 수 있습니다. 그렇게 계속해서 dp[0]과 dp[1]을 변경해주다, dp[n]의 값이 m과 일치하면 dp[0]과 dp[1]을 출력하는 방식입니다.
원래는 수학을 이용하여 dp[n]에 dp[1]과 dp[n]이 몇 개 들어있는지 규칙을 찾으려 했으나, 규칙이 없어서 그냥 코딩으로 푸는게 낫다고 판단했습니다.
꼭 출력하고 System.exit(0)을 하여 그 이상의 for문을 가동하는 일이 없어야 정답이 출력됩니다. 유념해주시기 바랍니다.
감사합니다.
728x90
반응형
'백준 문제 풀이' 카테고리의 다른 글
[BOJ - JAVA] 14002 - 가장 긴 증가하는 부분 수열(DP, LIS) (0) | 2021.11.10 |
---|---|
[BOJ - JAVA] 2775 - 부녀회장이 될테야(수학, DP) (0) | 2021.11.09 |
[BOJ - JAVA] 2156 - 포도주 시식(DP) (0) | 2021.11.07 |
[BOJ - JAVA] 16922 - 로마 숫자 만들기(DP, 조합) (0) | 2021.11.05 |
[BOJ - JAVA] 5550 - 헌책방(백트래킹, DP) (0) | 2021.11.04 |