양팔 저울( BOJ 1653 )

문제

1653. 양팔 저울 : https://www.acmicpc.net/problem/1653

1653번: 양팔 저울

 

문제 파악하기

• 추는 1g, 2g, ... , 9g까지 최대 9개가 있습니다.
• 양팔 저울에는 눈금이 5개씩 있으며, 평형을 이루게 만드는 추의 배치를 '평형정수'로 표현할 수 있으며, K번째 평형정수를 찾아야 합니다.
• 단순히 첫 번째 위치부터 추를 하나씩 놓으면 시간초과에 걸릴 수 있습니다.
• 어떤 방법으로 탐색을 해야 할까요?

 

문제 해결하기

• 추를 놓은 위치는 00001 ~ 98765 사이의 정수로 표현할 수 있습니다.
  반대로 말하면 추는 항상 1 ~ 98765 사이의 정수로 표현됩니다.
• 따라서 1 ~ 98765의 모든 정수에 대해, 계산되는 무게를 기준으로 정수를 나눠서 저장할 수 있습니다.
• 무게 별로 정수 2개를 한 쌍으로 묶어서 현재 가지고 있는 추로 표현할 수 있는 쌍인지 확인할 수 있습니다.
• 만약 현재 추로 만들 수 있는 한 쌍의 정수라면 서로 앞에 배치했을 때와 뒤에 배치했을 때의 평형 정수를 하나의 배열에 모아두면 됩니다.
• 모든 탐색이 끝나면 배열을 정렬한 후, K번째 평형 정수를 출력하면 됩니다.

 

소스 코드

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define NMAX 10
#define VMAX 120
#define PAIR pair<int,int>
using namespace std;
 
// 입력 변수
int n, k, t;
int inp[NMAX];
 
// 탐색 변수
vector< int > val[VMAX];
vector< long long int > v;
 
// 결과 변수
long long int ret;
 
bool chk(int k) {
    int arr[NMAX]={0,};
 
    while(k>0) {
        arr[k%10]++;
        k /= 10;
    }
 
    for(int i=1;i<NMAX;i++) {
        if(arr[i] > inp[i]) return 0;
    }
 
    return 1;
 
}
 
int calc(int val) {
    int ret=0;
 
    for(int i=1;i<=5 and val>0;i++) {
        ret += i*(val%10);
        val /= 10;
    }
 
    return ret;
}
 
int convert(int val) {
    int ret=0;
 
    for(int i=1;i<=5;i++) {
        ret = ret*10 + val%10;
        val /= 10;
    }
 
    return ret;
}
 
bool isOk(int a, int b) {
    int arr[NMAX]={0,};
 
    while(a>0) {
        arr[a%10]++;
        a /= 10;
    }
 
    while(b>0) {
        arr[b%10]++;
        b /= 10;
    }
 
    for(int i=1;i<NMAX;i++) {
        if(arr[i] > inp[i]) return 0;
    }
 
    return 1;
}
 
 
int main() {
    // input
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d", &t);
        inp[t] = 1;
    }
    scanf("%d", &k);
 
    for(int i=1;i<=98765;i++) {
        if(!chk(i)) continue;
 
        val[calc(i)].push_back(i);
 
    }
 
    for(int num=1;num<VMAX;num++) {
        if(val[num].size() == 0) continue;
 
        for(int i=0;i<val[num].size();i++) {
            for(int j=i+1;j<val[num].size();j++) {
 
                if(isOk(val[num][i], val[num][j])) {
                    v.push_back(val[num][i]*1LL*100000 + convert(val[num][j]));
                    v.push_back(val[num][j]*1LL*100000 + convert(val[num][i]));
                }
            }
        }
    }
 
    v.push_back(0);
    sort(v.begin(), v.end());
 
    if(k>=v.size()) printf("%lld", v.back());
    else printf("%lld", v[k]);
}
 

 

후기

나름 구현하기 복잡했던 문제라고 생각합니다. 추의 특성도 고려해야 시간초과에 걸리지 않기 때문에 나름 까다로운 문제이며, 브루트포스 알고리즘의 심화 문제로 추천하고 싶습니다.