카테고리 없음

태어난김에 세계일주1

Kim David 2025. 7. 3. 04:30

태어난김에 세계일주 1

준석이는 태어난김에 세계 일주를 꿈꾸며 가능한 한 많은 나라를 방문하려 합니다. 하지만 각 나라에는 입국 규정이 있어, 입국하기 위해서는 일정 금액 이상의 잔고가 필요하며, 여행을 마칠 때마다 일정 금액의 경비가 소모됩니다.

여행자의 현재 통장 잔고 balance와, 각 나라별 "입국 필요 잔고" 및 "여행 경비"가 담긴 2차원 배열 countries가 주어질 때, 여행자가 방문할 수 있는 최대 국가 수를 반환하는 solution 함수를 작성하세요.

입출력 예시

예시 1:

  • 입력: balance = 600, countries = [[70, 350], [100, 550], [350, 400]]
  • 출력: 3
  • 설명: 1 → 0 → 2 방문
    • countries[1] (최소 550 필요, 100 사용) → 남은잔고: 500
    • countries[0] (최소 350 필요, 70 사용) → 남은잔고: 430
    • countries[2] (최소 400 필요, 350 사용) → 남은잔고: 80

예시 2:

  • 입력: balance = 500, countries = [[250, 250], [300, 400], [120, 450], [70, 150]]
  • 출력: 3
  • 설명: 2 → 3 → 0
    • countries[2] (최소 450 필요, 120 사용) → 남은잔고: 380
    • countries[3] (최소 150 필요, 70 사용) → 남은잔고: 310
    • countries[0] (최소 250 필요, 250 사용) → 남은잔고: 60

제한 사항

  • balance는 1 이상 3,000 이하의 자연수입니다.
  • countries의 길이(즉, 여행 가능한 나라의 개수)는 1 이상 7 이하입니다.
  • country[i] = [Ai, Bi]
    • Ai: 그 나라를 방문할 때 소모되는 금액 (1 ≤ Bi ≤ 500)
    • Bi: 입국을 위해 필요한 최소 잔고 (1 ≤ Ai ≤ 500)
  • 항상 Bi ≥ Ai (즉, 여행 비용은 입국 필요 잔고보다 클 수 없음)

 

 

- 문제 분석

주어진 초기 잔고 balance로 최대한 많은 나라를 방문함

각 나라를 방문하려면 현재 잔고 >= 입국 최소 필요 잔고(Bi) 여야 입국 가능

입국하면 잔고에서 경비(Ai)만큼 차감됨

나라들은 중복 없이 한번씩만 방문 가능함

방문 순서가 중요함 -> 순서에 따라 가능한 나라 수가 달라질 수 있음

 

- 접근 방법

각 나라 : [경비, 입국 최소 잔고]

즉, 방문 전에 balance >= Bi인지 확인, 방문하면 balance -=Ai

 

각 순열에 대해 최대 방문 가능한 나라 수를 계산하고

최댓값을 갱신해서 리턴하면 됨.

 

백트래킹으로

- 현재 잔고에서 방문 가능한 나라들을 하나씩 시도하며 재귀적으로 탐색

- 방문한 나라는 중복되지 않게

- 재귀 호출시 방문 여부, 잔고 업데이트

- 최대 방문수를 갱신해가며 최댓값 찾기

 

구현 과정

방문한 지역을 판별해주어야하기 때문에 방문 배열을 선언해줍니다.

 boolean[] visited = new boolean[countries.length];

 

그 후 재귀함수를 통해 순열 조합으로 가지고있는 잔고가 Bi보다 큰지 판별해주고 만약 크다면 해당 나라를 방문해주고

해당 나라의 Ai를 빼고 count를 증가한 값을 통해 재귀함수를 호출해줍니다.

  private void dfs(int balance, int count, int[][] countries, boolean[] visited) {
        maxCountries = Math.max(maxCountries, count);
        for (int i = 0; i<countries.length; i++) {
            int Ai = countries[i][0];
            int Bi = countries[i][1];

            if (!visited[i] && balance >= Bi) {
                visited[i] = true;
                dfs(balance - Ai, count+1, countries, visited);
                visited[i] = false;
            }
        }
    }

 

최종 코드

import java.util.*;
class Solution {
    private int maxCountries;
    public int solution(int balance, int[][] countries) {
        maxCountries = 0;
        boolean[] visited = new boolean[countries.length];
        dfs(balance, 0, countries, visited);
        return maxCountries;
    }

    private void dfs(int balance, int count, int[][] countries, boolean[] visited) {
        maxCountries = Math.max(maxCountries, count);
        for (int i = 0; i<countries.length; i++) {
            int Ai = countries[i][0];
            int Bi = countries[i][1];

            if (!visited[i] && balance >= Bi) {
                visited[i] = true;
                dfs(balance - Ai, count+1, countries, visited);
                visited[i] = false;
            }
        }
    }
}