[백준] 34030 So☆Lucky - C++

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

---

이왜골

 

천코대 예선에 직접 나가서 이 문제를 접했다.

애드훅 실버 1~2 문제인 줄 알고 무지성으로 풀었다..

근데 대회가 끝나고 보니 티어가 골드3인게아닌가!!!!!!

분명 올려치기 당한게 분명하다.

 

문제 자체는 간단하다.

주어진 수열을 오름차순 정렬하려고 하는데,

1. i번째 값과 i+1번째 값의 합이 홀수일 때 두 값을 교환한다.

2. i번째 값과 i+1번째 값의 합이 짝수일 때 두 값을 교환한다.

이 둘 중 한 연산'만' 사용해 정렬하고, 정렬이 되면 So lucky,

안되면 Unlucky를 출력한다.

 

진짜 무지성으로 풀었고

문제에서 원하는 코드가 절대 이런 코드가 아니라고 확신 할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[200001];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int is_hol = 1;
    int is_jak = 1;
    for (int i = 0; i < n - 1; i++) {//연산1=홀수
        if (arr[i] > arr[i + 1] && (arr[i] + arr[i + 1]) % 2 == 0) {
            is_hol = 0;
            break;
        }
        if (i > 0) {
            if (i < n - 2) {
                if ((arr[i - 1] > arr[i + 1] && (arr[i - 1] + arr[i + 1]) % 2 == 0) || (arr[i] > arr[i + 2] && (arr[i] + arr[i + 2]) % 2 == 0)) {
                    is_hol = 0;
                    break;
                }
            }
        }
    }
    for (int i = 0; i < n - 1; i++) {//연산2=짝수
        if (arr[i] > arr[i + 1] && (arr[i] + arr[i + 1]) % 2 != 0) {
            is_jak = 0;
            break;
        }
        if (i > 0) {
            if (i < n - 2) {
                if ((arr[i - 1] > arr[i + 1] && (arr[i - 1] + arr[i + 1]) % 2 != 0) || (arr[i] > arr[i + 2] && (arr[i] + arr[i + 2]) % 2 != 0)) {
                    is_jak = 0;
                    break;
                }
            }
        }
    }
    if (is_hol) {
        cout << "So Lucky\n";
    }
    else {
        cout << "Unlucky\n";
    }
    if (is_jak) {
        cout << "So Lucky\n";
    }
    else {
        cout << "Unlucky\n";
    }
    return 0;
}

언버블리버블!!

코드를 얼마나 더럽게 짰으면

if문 조건식이 한 화면에 담기지도 않는다!!

솔직히 나도 이 코드가 왜 정답인지 모르겠지만, 일단 간략한 코드 설명을 하자면...

 

큰 for문이 두개 있는데, 홀수연산 짝수연산을 각각 수행해 결과를 뽑기 위함이다.

진짜 정렬을 해보며 결과를 얻는 방법도 있었겠지만 시간복잡도를 O(n)으로 만들어야 한다는 압박감 때문에

저런 엄청난 코드가 탄생했다.

 

for문 안에서는 i를 증가해가며 검사하는데, 편의상 index가 0에 가까울수록 앞, 멀수록 뒤라고 하겠다.

(+홀수연산 기준으로 설명하겠다.)

첫번째 if문 : 현재 값(i번째 값)과 뒤의 값이 오름차순이 아니여서 정렬할 필요가 있는데

만약 둘이 더한게 짝수다?? 그럼 절대 홀수연산만으로 정렬할 수 없기 때문에 is_hol을 0으로 바꾸고 break한다.

 

is_hol이라는 변수 이름이 상당히 애매해서 설명하자면, 홀수연산으로 정렬할 수 있는 배열이면 1, 아니면 0을 가진다..

 

두번째 if문 : 첫번째 if문을 통과해도 홀수연산만으로 정렬할 수 없는 경우가 존재한다.

교환자체는 가능해서 교환한 경우인데, 교환 한 후 그 앞이나 뒤의 값과 충돌하거나.. 아무튼 있다. 알아서 찾아보길.

따라서 교환을 했다고 가정한 상태에서 검사를 해줘야 한다.

원소를 직접 교환하는 방식이 아니라 약간 예상해서 검사한다는 느낌이다.

현재 값 바로 뒤의 값과, 현재 값 바로 앞의 값을 비교해서

(현재값과 바로 뒤의 값이 교환된다면 이 둘이 충돌할 수도 있게 되기 때문에)

홀수연산만 사용해 오름차순이 된다면 ㅇㅋ이다.

현재값과, 현재 값 2칸 뒤의 값도 비교해서 (위와 같은 이유)

홀수연산만 사용해 오름차순이 된다면 ㅇㅋ이다.

이 두가지 조건을 하나라도 만족하지 못하면, 매우 unlucky하기 때문에 is_hol을 0으로 바꾸고 break한다.

 

짝수 연산도 위의 과정에서, 단지 더해서 홀수냐 짝수냐만 바꾼것이다.

---

근처 세네칸만 비교하는 로직인데 왜 맞는지 모르겠다.

아무튼 풀었으니 된거 아닐까.....

천코대 본선을 위해 열심히 알고리즘 공부를 하도록 하자.....

---