백준 14697 방 배정하기 Java

문제집에 있는 문제를 무작위로 풀어보던 도중 만난 문제이다.

문제를 보자마자 백준 2839번 설탕 배달 문제가 생각났다.

그래서인지 설탕 배달을 풀었을 때 처럼 풀어보려고 노력을 해봤지만

설탕 배달 문제와는 다른 부분이 많아서 설탕 배달 처럼 풀지는 못하였다.

 

우선 세 개의 수가 주어지는데 세 가지의 수를 전부 안써도 된다.

하나의 수로만 주어진 인원을 꽉채워도 되고 두 개의 수도 되고.. 세 개의 수도 되고

어떻게 풀어야할지 도저히 감이 안잡혔다.

 

주어진 수의 배수를 모두 저장하고 배수들 끼리 더해보는 방법도 생각해봤지만

아무리 생각해도 그렇게 푸는건 아닌 것 같았다.

근데 그런식으로 푸는게 맞았다..

 

나올 수 있는 경우의 수를 다 더해보는...

이것을 완전탐색 또는 브루트포스(brute force)알고리즘 이라고 한다는 것도 알게 되었다.

다른 분들이 푼 것을 보면 내가 생각했던 것보다 훨씬 라인 수가 적고 간단하게 풀어서

감탄했다.

a, b, c를 세 개의 수라고 하고

인원을 n이라고 했을 때

 

for(int i=0; i<=50; i++)

  for(int j=0; j<=50; j++)

    for(int k=0; k<=50; k++)

      if( (a * i) + (b * j) + (k * c) == n)

          answer = 1;

 

이런 식으로 3중 for문을 이용해 완전 탐색을 하면 귀찮게 배수를 구하는 등 하지 않아도

경우의 수를 모두 비교해볼 수 있다. 한 개의 수로만으로도 되는 경우도 i와 j가 0인 경우가 있기 때문에

마찬가지로 두 개의 수로만 되는 경우도 i가 0인 경우가 있기 때문에

찾을 수 있는 것이다. i,j,k가 50이하인 이유는 문제에서 주어진 범위이다.

물론 더 효율적으로 짤 순 있겠지만 이렇게 간단하게도 짤 수 있다는게 신기했다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int n = scan.nextInt();
        int ans = 0;
        
        for(int i=0; i<=50; i++)
            for(int j=0; j<=50; j++)
                for(int k=0; k<=50; k++)
                    if((a*i) + (b*j) + (c*k) == n)
                        ans=1;
        
        System.out.println(ans);
    }