본문 바로가기

728x90

backtracking2

[BOJ] 2529번 - 부등호 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족하는 수열을 구해야한다. → 이 수열을 구하기 위해 백트래킹 방식을 사용한다. 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. → 백트래킹을 할 때 사용할 배열은 위와 같고 중복되지 않는 값들로 이뤄지도록 visited 배열을 사용한다. 이제 여기서 모든 부등호 관계를 만족하는 수열 중 가장 큰 값과 가장 작은 값을 구해야한다. 이때 주의할 점은 첫 자리가 0인 경우도 정수에 포함해야한다. 즉, 0123과 같이 출력해야한다. 나는 이를 쉽게 다루기 위해 문자열로 답을 구하기로 했다. 그러나 최솟값.. 2024. 3. 11.

[Softeer] Lv3. 택배마스터 광우 (Java) 1. 문제 문제 링크 : Lv3. 택배마스터 광우 주제 : 완전탐색, 백트래킹 2. 풀이 과정 및 정리 이 문제에서는 레일을 어떤 순서로 돌아서 최소한의 무게로 일할 수 있는지 찾아야한다. 위의 그림과 같이 레일을 돌면서 바구니 무게를 초과하기 전까지는 무조건 1번으로 시행되어야 한다. 이는 딱히 규칙성이나 공식을 찾을 수 없다. 그래서 내가 선택한 방식은 완전탐색을 하여 레일의 순서를 모두 구했다. 이를 구하기 위해서 아래와 같이 백트래킹 방식으로 순서를 구했다. static void dfs(int count, int[] result) { if(count == n) { //순서가 정해졌을 경우 int w = getWeight(result); minWeight = Math.min(w, minWeight).. 2024. 2. 25.

이전 1 다음

728x90

티스토리툴바