Seren dev's blog
article thumbnail

https://school.programmers.co.kr/learn/courses/30/lessons/87946

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

1. 풀이 - 순열(DFS)

던전을 탐험할 수 있는 모든 경우를 구하고, 탐험한 던전 수를 구한다. 탐험한 던전 수가 모든 던전의 개수와 같다면 더 이상 탐색하지 않는다.

던전을 탐험할 수 있는 모든 경우는 순열(DFS)을 사용하여 구했다.

1.1. 코드

<java />
class Solution { static int size; static int[] pm; static boolean[] check; static boolean flag; static int answer = 0; public int solution(int k, int[][] dungeons) { size = dungeons.length; pm = new int[size]; check = new boolean[size]; permutation(0, k, dungeons); return answer; } public static void permutation(int L, int k, int[][] dungeons) { if (flag) return; // 최댓값이 나왔으므로 더 이상 탐색할 필요가 없다 if (L == size) { int cnt = count(k, dungeons); answer = Math.max(answer, cnt); if (answer == size) { // 최댓값이 나왔으므로 flag를 true로 업데이트 flag = true; } return; } for (int i = 0; i < size; i++) { if (!check[i]) { pm[L] = i; check[i] = true; permutation(L+1, k, dungeons); check[i] = false; } } } public static int count(int k, int[][] dungeons) { int user = k; int cnt = 0; for (int idx : pm) { if (user >= dungeons[idx][0]) { user -= dungeons[idx][1]; cnt++; } } return cnt; } }

2. 다른 풀이 - DFS(순열 X)

위의 풀이는 순열을 사용하여 던전의 순서를 저장했지만, 따로 저장할 필요 없이 DFS를 사용해도 모든 경우의 수를 구할 수 있다.

<java />
class Solution { static int size; static boolean[] visited; static boolean flag; static int answer = 0; public int solution(int k, int[][] dungeons) { size = dungeons.length; visited = new boolean[size]; dfs(0, k, dungeons); return answer; } public static void dfs(int len, int k, int[][] dungeons) { if (flag) return; // 최댓값이 나왔으므로 더 이상 탐색할 필요가 없다 for (int i = 0; i < size; i++) { if (!visited[i] && dungeons[i][0] <= k) { visited[i] = true; dfs(len+1, k - dungeons[i][1], dungeons); visited[i] = false; } } answer = Math.max(answer, len); if (answer == size) { // 최댓값이 나왔으므로 flag를 true로 업데이트 flag = true; } } }
728x90
profile

Seren dev's blog

@Seren dev

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!