[BOJ]1660번 : 캡틴 이다솜

https://www.acmicpc.net/problem/1660

1660번: 캡틴 이다솜

 

 

분류 : 다이나믹 프로그래밍, 동전 교환

 

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

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str += br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) throws Exception {
        int N = sc.nextInt();
        int[] dp = new int[125];
        boolean[] visited = new boolean[300001];
        Queue<Integer> q = new LinkedList<>();
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < 122; i++) {
            dp[i] = ((i + 1) * i) / 2 + dp[i - 1];
        }
        q.offer(0);
        int depth = 0;
        visited[0]=true;
        loop1: while (!q.isEmpty()) {
            int size = q.size();
            for (int sz = 0; sz < size; sz++) {
                int here = q.poll();
                if (here == N) {
                    break loop1;
                }
                for (int i = 0; dp[i] <= N; i++) {
                    int there = here + dp[i];
                    if (there > N || visited[there])
                        continue;
                        visited[there]=true;
                        q.offer(there);
                }
            }
            depth++;
        }
        out.println(depth);
        out.flush();
    }
}

 

풀이 방법 : 다른 사람들은 dp를 통해 푼 것 같지만 나는 BFS를 활용하여 풀이해보았다.

 

일단 30만 이하의 각 사면체에 필요한 대포알 개수를 저장해놓고 현재 갯수를 q에 넣어가며 N과 현재 개수가 같을 경우 While문을 탈출하여 depth를 출력

처음에 for(int i=0;dp [i]<N;i++) 식으로 했다가 한번 틀려서 for(int i=0;dp [i]<=N;i++)으로 수정해줬더니 바로 통과되었다.

흠.. 뭔가 딱히 어려운 코드 부분은 없는 것 같다.