백준 15883 (C++) First In Last Out

최초 업로드: 2025-07-21 19:12:47

최근 수정 시간: 2025-07-21 22:07:59

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] First In Last Out

[문제 링크](https://www.acmicpc.net/problem/15883)

## 문제 설명

다음 16진법 식이 성립하도록 각 영문자에 0 ∼ f 사이의 16진수를 배정하라.

단, 서로 다른 영문자에는 서로 다른 숫자가 배정되어야 하며, 각 수의 첫 글자는 0이 될 수 없다.

## 입력

없다.

## 출력

첫 번째 줄부터 모든 해답을 한 줄에 한 개씩 사전순으로 출력한다.

각 해답은 LIST + FILO = STACK 의 형태로 16진수로 표현해야 하며, a, b, c, d, e, f 는 소문자이다.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f 의 순서를 사전순으로 간주한다.

## 풀이
#### 백트래킹으로 접근하였다. 같은 문자 처리하는 부분 구현하는 것이 귀찮았던 것만 빼면 쉬운 문제였다. 지금보니 시간 줄이기 위한 중복처리는 빼고, 텍스트로 제출했으면 더 쉬웠을 것 같다.

``` c++
#include<bits/stdc++.h>
using namespace std;

char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
int val[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int used[16];
int chIdxA[8], chIdxB[8];
char a[8], b[6];

int hexToDec(int s, int e) {
    int sum=0, cur=1;
    for(int i=e;i>=s;i--) {
        sum += cur * val[chIdxA[i]];
        cur *= 16;
    }
    return sum;
}

bool decToHex(int val) {
    bool chk=true;
    for(int i=4;i>=0;i--) {
        b[i] = ch[val%16];
        chIdxB[i] = val%16;
        if(++used[val%16]>=2 && i>1) chk=false;
        val /= 16;
    }
    return chk && b[0]!='0' && a[2]==b[0] && a[3]==b[1];
}

void dfs(int depth=0) {
 if(depth==6) {
 a[7] = a[5];
 a[5] = a[1];
 a[6] = a[0];
 chIdxA[7] = chIdxA[5];
 chIdxA[5] = chIdxA[1];
 chIdxA[6] = chIdxA[0];
 if(decToHex(hexToDec(0, 3) + hexToDec(4, 7))) cout << a[0] << a[1] << a[2] << a[3] << " + " << a[4] << a[5] << a[6] << a[7] << " = " <=0;i--) used[chIdxB[i]]--;
 return;
 }
 for(int i=0;i<16;i++) {
 if((depth==0 || depth==4) && i==0) continue;
 if(!used[i]) {
 a[depth] = ch[i];
 chIdxA[depth] = i;
 used[i]++;
 dfs(depth+1);
 used[i]--;
 }
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    dfs();
}
```