https://www.acmicpc.net/problem/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++)으로 수정해줬더니 바로 통과되었다.
흠.. 뭔가 딱히 어려운 코드 부분은 없는 것 같다.
'PS' 카테고리의 다른 글
[BOJ] 2512번 - 예산 (0) | 2017.05.29 |
---|---|
[BOJ]2526번 : 싸이클 (0) | 2017.05.01 |
[BOJ]5052번 : 전화번호 목록 (0) | 2017.04.24 |
[BOJ]8983번 : 사냥꾼 (0) | 2017.04.22 |
[BOJ]2352번 : 반도체 설계 (0) | 2017.04.20 |