[BaekJoon/백준] 14889번 & 다시보기 ★★★★★

이 문제를 통해 벽을 느꼈다. 세상에는 정말 똑똑한 사람들이 많다.

 

 

문제를 코드로 구상하는 과정에서, 최대한 코드를 줄여서 짜고 싶었다.

그리고 일단 문제는 조합 + 순열 로 풀 생각이였다.

 

1 ~N 까지 N/2 개 뽑아서 한 팀 만들고, 그 값을 또 순열을 시행한 뒤에 한 팀의 값을 얻어낸다.

그리고 조합으로 뽑은 값을 반전시켜준 뒤 다시 수열을 시행하여 다른 팀의 값을 얻어낸다.

 

위 방식대로 코드를 구성하여서, 시간도 오래걸려서 풀긴 했는데 코드가 너무 무거웠다.

 

그래서 다른 분들의 코드를 찾아보기 시작했고, 벽을 느꼈다.

 

 

일단, 나의 코드에서 꺼림칙한 부분이 두 군데 있었다.

1. 조합 + 순열 방식으로 푸는게 맞는지

2. 배열은 얼마나 필요한지

3. 조합으로 뽑을 때, A팀이 1 2 3이고 B팀이 4 5 6일 때와 A팀이 4 5 6이고 B팀이 1 2 3일때의 결과는 같기에, 이 조합 과정을 줄이고 싶은데, nCr 값을 기준으로 하자니 코드만 더 늘어날 것 같다.

 

 

 

1번은, 다른 분들의 풀이를 보며 개선할 수 있었다.

조합을 통해 팀을 뽑은 뒤에 순열로 나열하는 것이 아니라, 전체 배열에서 뽑은 것들을 제외한 나머지는 안뽑힌 것들이라는 사실에 이중포문을 사용해 풀 수 있었다. 

 

예를들어 1 2 3 4 5 6 이 있을 때, 1 2 3을 뽑았다면 4 5 6은 안뽑혔다는 것이고, 뽑힌 1 2 3 따로 안뽑힌 4 5 6 따로 각각 이중포문을 돌려가며 숫자들을 나열해주면 된다. (단 11 12 13 21 22 23 31 32 33 이런식으로 뽑히겠지만 11 22 33은 0값이라 상관없고, 굳이 필터링해주자면 해줄 수도 있음)

 

내가 너무 순열과 조합에만 목을 메고 있었다.

 

또한 2번도, 다른 분들의 풀이를 보며 개선할 수 있었다.

처음에는 '뽑은 숫자' 들을 나타날 배열과, '뽑힌 상태'를 체크할 배열 두 개를 이용했었다.

하지만 이 문제에서는 그냥 '뽑힌 상태'를 체크할 배열 하나만 가지고도, 해당 인덱스를 통해 '뽑은 숫자'를 나타낼 수 있는 상황이였다.

 

그렇게 종합해서 만든 코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

int arr[20][20], p[20];
int nx, min = 4500;
int result_a = 0, result_b = 0;

void pp() {
    // 1 2 3 4 5 6 있다고 볼 떄
    // 1 2 3 뽑혔으면 4 5 6은 안뽑혔을 것.
    // 그럼 1 2 3으로 이중포문, 4 5 6으로 이중포문 돌려서 따로 계산.
    // 11 12 13 21 22 23 31 32 33 이런식으로 뽑히겠지만 11 22 33은 값이 0이여서 상관없고, 만약 꺼림칙하면 필터해주면 됨.
    // 순열 + 같은거 여러번 뽑아도 되는게 이중포문
    for(int i = 0; i < nx; i++) {
        for(int j = 0; j < nx; j++) {
            if(p[i] && p[j])
                result_a += arr[i][j];
            else if(!p[i] && !p[j])
                result_b += arr[i][j];
        }
    }
    min = MIN(min, abs(result_a-result_b));
    result_a = result_b = 0;
}

// n = 이터레이터, count = 뽑은 갯수. 팀 나누기.
void zo(int n, int count) {
    if(count == nx/2) {
        pp();
        return;
    }
    for(int i = n; i < nx; i++) { // 절반만 해도 될까? 123 / 456 vs 456 / 123
        if(!p[i]) {
            p[i] = 1;
            zo(i + 1, count + 1);
            p[i] = 0;
        }
    }
}
int main() {
    int i, j;
    scanf("%d", &nx);
    for(i = 0; i < nx; i++) {
        for(j = 0; j < nx; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    zo(0, 0);
    printf("%d", min);
}

주석에 나의 고민이 나와 있듯이 3번째 고찰은 해결해내지 못했다.

문제에 대한 답은 틀리지 않아도, 코드 흐름이 똑같은 과정을 한번 더 불필요하게 반복한다. 이를 해결하기 위해 다른분들의 코드를 많이 봤지만, 대부분의 코드는 나와 같은 방식이였고, 읽기가 힘든 코드들은 이해하기도 어려웠다..ㅠ

 

그러다가 어떤 한 분의 코드가 눈에 들어왔는데, 굉장히 짧고 단순하면서도 뭔가 3번째 문제를 해결한 것 같이 보였다.

디버깅을 해보니 이 코드는 불필요한 과정을 한번 더 반복하지 않는다.

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int n;
int arr[23][23];
int ans = 2147483647;
int team[23];

void solve(int count, int index) {
    if (index == n) return;
    if (count == (n / 2)) {
        int score1 = 0, score2 = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (team[i] == 1 && team[j] == 1) {
                    printf("%d %d\n", i, j);
                    score1 += arr[i][j]; }
                else if (team[i] == 0 && team[j] == 0) {
                    printf("%d %d\n", i, j);
                    score2 += arr[i][j]; }
            }
        }
        ans = min(ans, abs(score1 - score2));
        return;
    }
    team[index] = 1;
    solve(count + 1, index + 1);
    team[index] = 0;
    solve(count, index + 1);
}
// 0 1 / 2 3
// 0 2 / 1 3
// 0 3 / 1 2
// -> 거꾸로 한번 더 안함.
int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }
    solve(0, 0);
    printf("%d\n", ans);
    return 0;
}

근데 문제는 도저히 코드를 이해할 수가 없다는 것 ㅜㅜㅜ 순수하게 재귀적인 함수다.

이건 나중에 시간될 때 상향식/하향식 분석을 해봐야겠다.

 

+ 하향식 분석을 해보긴 했는데, 이걸 어떻게 짜는지 이해가 안된다 ㅋㅋ..

 

+ 3을 뽑으면 다음 작업이 무조건 아무것도 못하도록 ( 3을 뽑아서 출력하는 경우가 없도록 = 3을 못뽑도록 ) 흐름이 돌아가고 있는 것 같다는 게 보이기 시작...!! -> x, 3인 상태에서 3을 뽑고 어떤 함수를 호출해도 4가 되므로 탈출하게 되어있음. 

 

 

-> 위 분석을 토대로, 숫자 하나를 뽑지 않음으로써 문제에서 생기는 중복 경우를(문제에선 ABC/DEF = DEF/ABC) 제거할 수 있다는 걸 깨달음. 아예 하나를 뽑지 않으면 조합 알고리즘의 횟수가 절반으로 줄고, 뽑은 것들을 뽑지 않았던 것들을 각각 그룹화 시키는 과정에서 중복이 없어짐(말로표현하가 힘드네.. 위 그림의 아래 숫자 나열 참고)

#include <stdio.h>
#include <stdlib.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

int arr[20][20], p[20];
int nx, min = 4500;
int result_a = 0, result_b = 0;

void pp() {
    // 1 2 3 4 5 6 있다고 볼 떄
    // 1 2 3 뽑혔으면 4 5 6은 안뽑혔을 것.
    // 그럼 1 2 3으로 이중포문, 4 5 6으로 이중포문 돌려서 따로 계산.
    // 11 12 13 21 22 23 31 32 33 이런식으로 뽑히겠지만 11 22 33은 값이 0이여서 상관없고, 만약 꺼림칙하면 필터해주면 됨.
    // 순열 + 같은거 여러번 뽑아도 되는게 이중포문
    for(int i = 0; i < nx; i++) {
        for(int j = 0; j < nx; j++) {
            if(p[i] && p[j])
                result_a += arr[i][j];
            else if(!p[i] && !p[j])
                result_b += arr[i][j];
        }
    }
    min = MIN(min, abs(result_a-result_b));
    result_a = result_b = 0;
}

// n = 이터레이터, count = 뽑은 갯수. 팀 나누기.
void zo(int n, int count) {
    if(count == nx/2) {
        pp();
        return;
    }
    for(int i = n; i < nx - 1; i++) { // 윗분의 '순수하게 재귀적'인 함수의 흐름을 참고해서, 숫자 하나를 아예 뽑지 않도록 해주니 작업이 원하던대로 줄어듦. -> 14/23 - 23/14 같이 문제에서 불필요하게 실행되던 경우가 없어짐. 3번 해결(뽑고 안뽑고로 팀이 나뉘는 특성 상, 조합 알고리즘을 돌다 보면 안뽑고 뽑고의 흐름으로 팀만 바뀐 경우가 존재하는데, 처음부터 하나를 아예 뽑지 않음으로써 해결됨.)
        if(!p[i]) {
            p[i] = 1;
            zo(i + 1, count + 1);
            p[i] = 0;
        }
    }
}
int main() {
    int i, j;
    scanf("%d", &nx);
    for(i = 0; i < nx; i++) {
        for(j = 0; j < nx; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    zo(0, 0);
    printf("%d", min);
}

zo 함수의 for문만 수정됨!! 돌려보니 속도가 절반으로 줄었따 ㅎㅎ. 그치만 이런 절반만 뽑는..?(nx - 1회 하면 횟수가 절반, 결과도 절반)유형 또 나와도 못 풀 것 같다 ㅜ 아직은 스며들지가 않아..(신기하게 nx - 1로 절반 뽑은것과 안뽑은 것들의 경우를 모으면 전체 조합 뽑는 경우(nx)와 같음)