[Week 7] NUMBERGAME self review - dakyommii

[dakyommii]

NUMBERGAME self review

1. 해결 시도 과정

처음에는 2개 이상 남았을 경우 왼쪽에서 삭제하는 경우, 오른쪽에서 삭제하는 경우, 하나 남았을 때 왼쪽에서 가져갈 경우, 오른쪽에서 가져갈 경우 모두 나눠서 접근할 수 있도록 시도했지만 그럴 경우에 누구 차례인지도 구분해줘야하고 각각의 점수를 계산하기 어려웠습니다.
이를 개선하기 위해 아예 return하기 전에 최대값을 판별해 처리한 후 return할 수 있도록 변경하였습니다. 또한 기본적으로는 숫자를 가져오는 것으로 하고 2개 이상일 경우에만 숫자를 삭제할 수 있도록 변경하고 숫자를 삭제하거나 가져오는 경우끼리도 최선의 값을 선택하도록 max함수를 활용해 비교하였습니다.

2. 아이디어

동적계획법을 시도하려고 했습니다.
숫자를 2개씩 삭제하거나 숫자를 가져가는 경우 현재 가리키는 인덱스값을 조절해서 가져오는 수를 계산하고자 하였습니다.
최선을 다해서 게임을 하는 설정이기에 최선의 값을 판별해주는 방법이 필요했습니다. 따라서 숫자를 가져오는 경우에는 오른쪽과 왼쪽에서 가져와보고 현우와 서하의 점수 차가 가장 큰 방법을 선택할 수 있도록 max함수를 활용하였습니다.
그리고 2개 이상 남았을 때는 왼쪽, 오른쪽 모두에서 2개를 삭제해보고 최댓값을 최종값으로 정할 수 있도록 했습니다.

3. 코드 설명

#include <iostream>
using namespace std;

int arr[50];
int n;

int a = 0, b = 0;

int loc(int l, int r) {
    if (l > r) return 0;    //남은 숫자 없는 경우

    int res = 0;
   
    res = max(arr[l] - loc(l+1,r), arr[r] - loc(l,r-1));
    
    //2개 이상 남았을 경우
    if (r - l + 1 >= 2) {
        res = max(res, -loc(l+2, r));   //왼쪽 2개 삭제
        res = max(res, -loc(l, r-2));   //오른쪽 2개 삭제
    }
    
    return res;
    
}

int main() {
    int C;
    
    cin >> C;
    
    while (C--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        cout << loc(0,n-1) << endl;
    }
}

4. 막힌 점 및 개선 사항

결과는 똑같이 나오는데 시간초과가 되어서 다른 방법으로도 시도해봐야할 것 같습니다. 코드면에서는 가장 단순하게 된 것 같은데 시간초과가 된 이유는 잘 모르겠습니다. 2개 이상 남았을 경우 처리하는 부분에서 이해가 더 필요하다고 느꼈기 때문에 이 부분을 다시 검토해볼 필요가 있을 것 같습니다.