[programmers] 1835번 - 단체사진 찍기(Brute force, 2017 카카오코드 본선)

1. 문제 및 예제

 

 주어진 조건을 보면 아무리 계산을 많이 해도 시간 제한에 걸리지 않을 것이라는 확신을 가졌다. 그리고 문제 풀이를 세울 때도 Brute force밖에 생각나지 않았다. 이 문제가 정답률이 낮은 이유는 문제 자체의 난이도가 아니라 전역 변수에 관한 처리 방법인 것 같다는 생각이 들었다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

---

2. 풀이과정

 

 문제를 나누면 다음과 같다.

 

1. 구할 수 있는 모든 순서를 구한다. (재귀함수 사용)

2. 순서가 구해지면 조건과 맞춰 answer 값을 계산한다.

 

- check_line() 함수

bool check_line(string line) {
    for (auto it : global_data) {
        int member1 = get_index(line, it[0]);
        int member2 = get_index(line, it[2]);

        if (it[3] == '=') {
            if (abs(member1 - member2) - 1 != (it[4] - '0'))
                return false;
        }
        else if (it[3] == '<') {
            if (abs(member1 - member2) - 1 >= (it[4] - '0'))
                return false;
        }
        else {
            if (abs(member1 - member2) - 1 <= (it[4] - '0'))
                return false;
        }
    }
    return true;
}

 

 문제에서 주어진 조건에 주어진 줄이 맞는지 맞지 않는지를 판단하는 함수이다.

 

- get_line() 함수

void get_line(int max, string line) {
    //검사 시작
    if (max == line.size()) {
        if (check_line(line)) {
            answer++;
        }
    }
    //순서 세우기
    else {
        for (int i = 0; i < 8; i++) {
            if (!visited[i]) {
                visited[i] = true;
                get_line(max, line + members[i]);
                visited[i] = false;
            }
        }
    }
}

 

 재귀함수를 사용하여 나올 수 있는 순서의 모든 경우의 수를 구하고 마지막까지 줄을 세운다면 check_line() 함수를 통해 answer를 계산하는 함수이다.

 

3. 결어

 

 실제 시험 환경처럼 연습이 필요하다는 것을 느꼈다.