[백준 17291번 / java] 새끼치기

문제

17291번: 새끼치기 (acmicpc.net)

풀이

dp문제다. 하지만 큐로 풀어도 풀릴 것 같길래 1시간 반동안 큐로 구현해봤지만 실패했다.

dp로 푸는 방법은 다음과 같다.

 

매년 1월에 작년 개체 수만큼 벌레가 새로 태어난다.

k가 홀수라면 k년도에 태어난 벌레들은 k+3년도에 죽는다.

k가 짝수라면 k년도에 태어난 벌레들은 k+4년도에 죽는다.

 

위 조건을 적용하여 벌레의 수를 구해보면 다음과 같은 규칙이 도출된다.

홀수년도에는 (작년 개체 수 * 2)마리

짝수년도에는 (작년 개체 수 * 2마리) - (3년 전 태어난 벌레 수) - (4년 전 태어난 벌레 수)마리

 

이때, 'i년도에 태어난 벌레 수' == 'i-1년도의 총 벌레 수'이다.

따라서 다음과 같이 변경할 수 있다.

홀수년도 : (작년 개체 수 * 2)마리

짝수년도 :  (작년 개체 수 * 2마리) - (4년 전 총 벌레 수) - (5년 전 총 벌레 수)

 

먼저 1, 2, 3, 4인 경우는 문제에서 주어졌으므로 dp배열에 기저값으로 입력한다.

5부터 20까지 반복하며 dp를 사용해 값을 구한다.

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        long[] dp = new long[21];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        dp[4] = 7;

        for(int i=5; i<=20; i++){
            dp[i] = dp[i-1]*2;
            if(i%2 == 0){
                dp[i] -= (dp[i-4] + dp[i-5]);
            }
        }

        bw.write(dp[N]+" ");
        bw.flush();
        bw.close();

    }
}

NOTE

• 스터디 시간에 풀었던 문제인데, 나 빼고 다 dp로 아주 간단하게 풀어서 맞춘 것을 보고 많은 것을 깨달았다.
  내가 실력 향상이 빠르게 안 되는 이유는 일단 문제 푸는 양이 적었고, 꾸준하지 못했던 것도 있지만 방향도 잘못되었던 것 같다. 
• 알고리즘 문제는 문제가 의도한 유형이 정해져있고, 그것을 빠르게 떠올려서 제한 시간 안에 풀이해야 한다. 여유를 가지고 이렇게 풀어도 되지 않을까? 하며 혼자 삽질하는 시험이 아니다. 
• 최대한 알맞은 유형을 떠올리는 연습을 해야겠다.
• 앞으로 스터디는 랜덤한 문제를 제한 시간 안에 풀 수 있는지 확인하는 용도가 되도록 평소에 더 노력해야겠다.