[BOJ/Java] 2502 : 떡 먹는 호랑이

문제

 

 

www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

 

 

 

풀이

 

 

할머니가 1일째에 받은 떡의 개수를 A개, 2일째에 받은 떡의 개수를 B개라고 하였을 때, D일째에는 ?*A + ?*B 개일 것이다. 또한 D일째에는 D-1일과 D-2일째의 떡의 개수를 합한 개수이다.

따라서 A와 B를 기준으로 1일부터 D일까지 식을 세워나간 뒤에 D일 째에 방정식을 풀어 정수인 A, B를 찾아내고 return 하도록 구현했다.

 

• 처음 설계

• 수정사항 / K 자체를 코드에서 수정해주었기 때문에 for문이 다시 돌아가고 i가 바뀔때마다 원본 K로 다시 만들어주어야 한다

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {// 떡 먹는 호랑이
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine());
		int D = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		count[] ricecake = new count[D + 1];
		
		ricecake[1] = new count(1, 0);
		ricecake[2] = new count(0, 1);
		
		for (int i = 3; i <= D; i++) {
			ricecake[i] = new count(ricecake[i - 1].A + ricecake[i - 2].A, ricecake[i - 1].B + ricecake[i - 2].B);
		}
		
		int originK = K;
		for (int i = 1; i <= K; i++) {
			K = originK;
			K -= ricecake[D].A * i;
			for(int j = i; j <= K; j++) {
				if(ricecake[D].B * j == K) {
					System.out.println(i);
					System.out.println(j);
					return;
				}
			}
		}
	}

	static class count {
		int A, B;

		count(int A, int B) {
			this.A = A;
			this.B = B;
		}
	}
}