프로그래밍/알고리즘

Softeer-연습문제-[한양대 HCPC 2023] Phi Squared(C++)(미해결)

Sechan Oh 2024. 3. 17. 23:54

문제 링크  https://softeer.ai/practice/7697/history?questionType=ALGORITHM

난이도 : Lv.3

문제 개요 : 

최후의 미생물의 크기 및 처음 위치 출력

틀린 이유 : 정직하게 구현했는데 왜 틀렸는지 모르겠다.

처음 제출했던 코드 : 하나씩 뽑아서 일일이 계산했다.

#include<iostream>
#include<vector>
#include<deque>

using namespace std;

int main(int argc, char** argv)
{
    int N;
    scanf("%d", &N);

    deque<vector<int>> dq;
    for(int i=0; i<N; i++){
        int tmp;
        scanf("%d", &tmp);
        dq.push_back({i+1, tmp});
    }

    while(dq.size() > 1){
        deque<vector<int>> tmp_dq(dq);
        dq.clear();
        while(!tmp_dq.empty()){
            int value = 0;
            vector<int> pick = tmp_dq.front();
            tmp_dq.pop_front();
            if(!dq.empty() && dq.back()[1] <= pick[1]){
                value += dq.back()[1];
                dq.pop_back();
            }
            if(!tmp_dq.empty() && tmp_dq.front()[1] <= pick[1]){
                value += tmp_dq.front()[1];
                tmp_dq.pop_front();
            }
            pick[1] += value;
            dq.push_back(pick);
        }
    }

    printf("%d\n%d", dq.front()[1], dq.front()[0]);

   return 0;
}

문제 해결 방법

1.