백준 2529 부등호

https://www.acmicpc.net/problem/2529

2529번: 부등호

#include<stdio.h>
using namespace std;
int k;
char d[10];
long long int chk[10];
int num[10];
void copy(char cchk[10], char chk[10])
{
    for (int i = 0; i < 9; i++) {
        cchk[i] = chk[i];
    }
}
bool chknum(int num, int idx) {
    if (idx == 0)return true;
    else {
        if (d[idx - 1] == '<') {
            if (chk[idx - 1] < num) {
                return true;
            }
            else return false;
        }
        else {
            if (chk[idx - 1] > num) {
                return true;
            }
            else return false;
        }
    }
}
void init() {
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf(" %c", &d[i]);
    }
}
long long int Max = -98765432100;
long long int Min =98765432100;
void dfs(int idx) {
    if (idx == k + 1) {
        long long int number = 0;
        for (int i = k, ten = 1; i>=0; i--,ten*=10) {
            number += (chk[i]) * ten;
        }
        if (Max < number)Max = number;
        if (Min > number)Min = number;
        return;
    }
    char cchk[10] = { 0, };
    for (int i = 9; i >=0; i--) {
        if (num[i]==0&&chknum(i, idx)) {
            num[i] = i+1;
            copy(cchk, d);
            chk[idx] = i;
            dfs(idx + 1);
            chk[idx] = 0;
            copy(d, cchk);
            num[i] = 0;
        }
    }
}
int main(void) {
    init();
    dfs(0);
    char numm[2][10] = { 0, };
    for (int i = k; i >= 0; i--) {
        numm[0][i] = (Max % 10) +'0';
        Max /= 10;
    }
    for (int i = k; i >= 0; i--) {
        numm[1][i] = (Min % 10 )+'0';
        Min /= 10;
    }
    for (int i = 0; i <= k; i++) {
        printf("%c", numm[0][i]);
    }
    printf("\n");
    for (int i = 0; i <= k; i++) {
        printf("%c", numm[1][i]);
    }
    printf("\n");
    return 0;
}

9 8 7 6 5 4 3 2 1 0 

을 주어진 부등호에 한개씩 넣어보는 방식으로  재귀에 넣기전에

chk num 함수를 만들어서 부등호의 조건과 부합한것만 넣었고 그렇게 뽑혀진경우

떨어져있는 숫자를 한개의 숫자로 만들었습니다.

즉, 8 9 4 2 이렇게 가능하다면

8942을 만들어 max 와 min을 갱신해주면서 

뽑고 여기서 원하는것이 혹시 0 2 1 을 뽑혔을때 21 이아닌 021을 출력을 해야하기 때문에

위의 식을 사용하여 문자열로 바꾸어 넣어주었습니다.

여기서 중요한것은 정수형을 문자형으로 바꿀수 있는가도 있지만 

'최소값과 최대값의 범위를 몇을 줄지였던것 같습니다.

최고로 크게 나오는값이 

9876543210 이기때문에  잘 주어야한다. 처음에 0x7fffffff를 줬는데 이경우 21억정도의 값이기때문에 값이 오버플로우

되서 값이 이상하게 된다. 

그래서 long long int로 사실 long long으로 해도 충분하다. 맥스와 민 값을 수정하여 문제를 해결했습니다.

 

오늘은 여기까지이고 아직까지 어렵지 않은 문제여서 쉽게 풀었습니다.

매일매일 즐거운 코딩합시다.