[백준/C++] 16936번 나3곱2

백준

 

---

🤔문제 이해

다음 값이 현재 값을 3으로 나눈 값이거나 2를 곱한 값으로 나열되어 있는 수열을 뒤섞어 놓은 게 입력으로 주어지고, 뒤섞기 전의 형태를 찾는 문제이다!

---

💡첫번째 아이디어

주어진 예제1에서는 N이 6이고 수열 B는 4 8 6 3 12 9였다. 각 숫자별로 이전에 올 수 있는 값(*2하기 전, /3하기 전 값)과 다음에 올 수 있는 값(*2한 후, /3한 후)을 적어보았다. 이전과 이후에 올 수 있는 값이 명확해 보여서 해당 방법을 가지고 구현해봤다.

해당 문제의 정답을 저장하는 자료구조는 앞 뒤로 넣고 뺄 수 있는 list를 사용하였다.

 

list를 채워넣기 위해 입력 값을 저장하는 배열을 0부터 n-1까지 for문으로 돈다.

list가 비어 있는 경우 이전에 올 수 있는 값과 다음에 올 수 있는 값이 해당 배열에 존재하면 순서에 맞게 list에 넣어주고,

list가 비어 있지 않는 경우 v[i]의 이전에 올 수 있는 값과 다음에 올 수 있는 값이 해당 배열에 존재하더라도 list의 맨 앞과 끝에 넣을 수 없으면 pass, 넣을 수 있으면 순서에 맞게 넣어주는 방식을 생각했다.

 

❌첫번째 제출(런타임에러 - IntegerOverflow)

IntegerOverflow가 발생.

문제의 조건에 수열 B에 포함된 원소가 10^18보다 작거나 같은 자연수임을 보지 못했었다...

int로 선언해준 변수들을 unsigned long long int로 바꿔주었고, bool타입의 exist 배열은 모든 값을 표현해줄 수 없어 빼고 고쳐서 다시 제출해주었다.

❌두번째 제출(런타임에러 - InvalidPointer)

이번엔 invalidPointer라는 에러가 떴는데 구글링을 해봤는데도 정확한 이유를 찾지 못했다.

벡터의 포인터 위치가 바뀌고 할당된 벡터의 포인터를 free()할 때 처음 할당시 선언한 벡터의 포인터 주소와 데이터가 추가된 후 바뀐 벡터의 포인터 주소가 달라 이러한 문제가 생긴다고 하는데 전혀 모르겠었다...

뭔가 Node 객체 배열에 문제가 있을 거라고 예상해서 map[i] = Node(a)를 해주던 것을 map[i].setting(a)라는 함수를 만들어 객체의 값들을 입력값으로 세팅해주었다.

❌세번째 제출(런타임에러 - InvalidPointer)

이번에도 InvalidPointer.

차라리 Node객체를 쓰지 않고 pair로 구성된 vector를 사용했다. 코드가 너무 지저분해졌지만 일단 맞추고자 하는 마음이 컸다. 

 

❌네번째 제출(런타임에러 - InvalidPointer)

역시나 InvalidPointer 에러가 떴다. 이 에러로 3,4시간을 고통받다 보니 결국 멘토한테 질문했다.

멘토님의 도움으로 깔끔하게 정리된 코드를 다시 제출해보았다.

❌다섯번째 제출(런타임에러 - InvalidPointer)

4번의 InvalidPointer 에러가 뜨고 나서야 애초에 이 방법이 잘못되었음을 알았다.🙄

만약 N=7이고 27 4 8 6 3 12 9 16이 순서대로 들어왔을 때 계속 고집하던 방법으로 하게 된다면

정답 배열에는 27 9 3 6 12 4까지만 들어가게 된다.

즉 27로 인해 들어간 27 9 때문에 4에서 이전값 12와 이후 값8이 있음에도 list의 앞 뒤에 존재해야 한다는 조건을 만족하지 못해 지나치게 된다 ! 

 

열심히 짠 코드를 한번에 지워버리고 문제를 다시 보았다.

 

---

💡두번째 아이디어

밥먹다가 불현듯 백트래킹이 생각났다 !

 

🔥풀이🔥

N이 100보다 작거나 같으므로 N^3보단 작으니 시간엔 문제 없을 것이라 생각했고, 한 값의 이후에 올 수 있는 수(/3 or *2)가 둘다 입력 배열에 존재하지 않다고 판단했다.

 

Solve함수 설명

1. Solve 함수 수행 전에 이미 입력 배열의 값을 정답 배열에 넣어줬으므로 n-2번만 반복문을 돈다.

2. n-2번 동안 입력 배열의 모든 값을 순회해서 정답 배열의 마지막 값을 /3하거나 *2한 값이 입력 배열에 있는 경우 정답 배열 맨 뒤에 넣어준다.

3. /3하거나 *2한 값이 없는 경우엔 continue

4. 바깥쪽 반복문이 n-2번째 돌 때 정답 배열의 크기가 N과 같다면 정답 배열을 출력, 같지 않다면 return 해준다.

 

❌여섯번째 제출(컴파일에러)

재귀를 사용해서 풀려다가 필요할 것 같았던 bool 타입의 visited를 초기화해주는 memset 함수를 사용했는데 #include <string.h>를 적지 않아 컴파일 에러가 떴다.🥲

종종 있었던 실수인데다 백준에서 알려줘서 금방 고쳤다.

⭕️일곱번째 제출(맞았습니다!!)

필요 없는 visited 배열을 없애주고 제출해서 정답이 떴다!

---

 

아래는 제출한 코드이다.

#include <iostream>
#include <vector>

using namespace std;
typedef unsigned long long ull;

vector<ull> v;
bool visited[101];
int n;

void Solve(vector<ull> ans) {
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (ans.back() % 3 == 0 && v[j] == ans.back() / 3) {
                ans.push_back(v[j]);
            } else if (v[j] == ans.back() * 2) {
                ans.push_back(v[j]);
            }
        }
        if (i == (n - 1)) {
            if (ans.size() == n) {
                for (int k = 0; k < n; k++) {
                    cout << ans[k] << " ";
                }
            } else {
                return;
            }
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    ull a;
    for (int i = 0; i < n; i++) {
        cin >> a;
        v.push_back(a);
    }
    for (int i = 0; i < n; i++) {
        vector<ull> ans;
        ans.push_back(v[i]);
        Solve(ans);
    }
}

 

재귀로 더 쉽게 풀 수 있었을 것 같은데 재귀를 잘 못해서 푸는 데 오래 걸린 것 같다.