문제 요약
시행 착오
1. 문제 이해
오랜만에 알고리즘 문제풀이를 하다보니 주어진 예시에 대한 이해가 부족했다. 맨 처음에 주어진 카운트만큼 반복문을 돌려야 하는데 왜 입력 숫자와 출력 숫자의 갯수가 다른지 고민했음..
2. 의도에 맞지 않은 답 출력
처음에는 문제를 제대로 이해하지 못해서 주어진 N 까지의 피보나치 과정을 전부 메모이제이션 한 뒤, N까지의 각 피보나치 수 중에서 모든 0과 1의 개수를 세었다.
실제 문제의 요구사항은 그것이 아닌 fibo(0)과 fibo(1)의 호출 횟수를 구하는 것이었고 다시 문제를 읽고 이를 파악하여 수정함
Solution
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int count = in.nextInt();
for (int i = 0; i < count; i ++) {
int targetNum = in.nextInt();
answer(targetNum);
}
in.close();
}
private static void answer(int targetNum) {
Pair[] fiboArr = new Pair[targetNum + 1];
for (int i = 0; i <= targetNum; i ++) {
fiboArr[i] = fibo(i, fiboArr);
}
System.out.println(fiboArr[targetNum].getZeroCnt() + " " + fiboArr[targetNum].getOneCnt());
}
private static Pair fibo(int num, Pair[] fiboArr) {
if (num == 0) {
return new Pair(1, 0);
} else if (num == 1) {
return new Pair(0, 1);
} else {
return new Pair(fiboArr[num - 1].getZeroCnt() + fiboArr[num - 2].getZeroCnt(),
fiboArr[num - 1].getOneCnt() + fiboArr[num - 2].getOneCnt());
}
}
static class Pair{
private int zeroCnt;
private int oneCnt;
public Pair(int zeroCnt, int oneCnt) {
this.zeroCnt = zeroCnt;
this.oneCnt = oneCnt;
}
public int getZeroCnt() {
return this.zeroCnt;
}
public int getOneCnt() {
return this.oneCnt;
}
}
}피보나치 수열은 해당 수가 2 이상일 때, N - 1, N - 2의 피보나치 결과의 합을 구하면 된다. 재귀를 통해 구할 수도 있었지만 문제 조건에 실행시간 제한이 있어서 메모이제이션 기법(DP)을 활용하였고 처음 문제를 잘못 이해했을 때에는 int 배열을 선언하여 단순한 피보나치를 계산하였다.
문제를 다시 이해하고 난 뒤 피보나치 수 대신 0, 1의 개수를 묶어서 배열에 저장하면 맨 마지막 칸의 0, 1의 수를 리턴하면 될것 같아서 Pair 클래스를 선언하여 0, 1의 개수를 저장했다(C++ 에는 STL에 pair가 있었는데 이 부분은 좀 불편한듯..).
피보나치 수를 구하든 0, 1의 수를 구하든 기존의 방식과 동일하므로 N - 1, N - 2의 칸에 있는 0, 1의 개수를 더해서 저장해 나갔으며, 여기서 포인트는 N까지 구해야 하므로 for문의 조건을 i < N 이 아닌 i ≤ N 으로 해야 한다는 점이다.
오랜만에 해서 시간이 좀 걸렸지만 문제만 잘 이해하면 풀기 어렵지 않은 문제였다(코테에도 lombok 적용가능하게 해주면 안되나...).
다른 Solution
생각해보니 아래 풀이처럼 Pair innerClass를 만들지 않고 2차원 배열로 해결해도 됐을것 같다..
import java.util.Scanner;
public class Main {
static Integer[][] dp = new Integer[41][2];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
dp[0][0] = 1; // N=0 일 때의 0 호출 횟수
dp[0][1] = 0; // N=0 일 때의 1 호출 횟수
dp[1][0] = 0; // N=1 일 때의 0 호출 횟수
dp[1][1] = 1; // N=1 일 때의 1 호출 횟수
int T = in.nextInt();
while(T-- > 0){
int N = in.nextInt();
fibonacci(N);
System.out.println(dp[N][0] + " " + dp[N][1]);
}
}
static Integer[] fibonacci(int N) {
// N에 대한 0, 1의 호출 횟수가 없을 떄(탐색하지 않은 값일 때)
if(dp[N][0] == null || dp[N][1] == null) {
// 각 N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출한다.
dp[N][0] = fibonacci(N - 1)[0] + fibonacci(N - 2)[0];
dp[N][1] = fibonacci(N - 1)[1] + fibonacci(N - 2)[1];
}
// N에 대한 0과 1, 즉 [N][0]과 [N][1] 을 담고있는 [N]을 반환한다.
return dp[N];
}
}
댓글