[Algorithm] Baekjoon 2879번 : 코딩은 예쁘게

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

2879번: 코딩은 예쁘게

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, temp, answer = 0;
    int zeroCount = 0;
 
    cin >> n;
 
    int arr[2][1001];
 
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> temp;
            arr[i][j] = temp;
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        arr[1][i] = arr[1][i] - arr[0][i];
    }
 
    // arr[1][i] 만큼 해야한다는것
 
    int index = 0;
 
    while (1)
    {
        int stand = arr[1][index];
 
        if (stand == 0)
        {
            ++zeroCount;
            ++index;
            continue;
        }
 
        //if (zeroCount == n) break;
 
        int minNum = abs(stand);
        int indexCount = 0;
 
        // 아래의 같은 부호의 연속된 수들 찾고 최소값 구하기.
        for (int i = index + 1; i < n; ++i)
        {
            if (arr[1][i] == 0) break; // 완성된거 만나면 바로 break.
 
            int poped = arr[1][i];
 
            if (stand * poped > 0) // 같은 부호면
            {
                ++indexCount;
                minNum = min(minNum, abs(poped)); // 절대값작은거.
            }
            else
            {
                break;
            }
        }
 
        answer += minNum;
 
        // 값 반영.
        for (int j = index; j <= index + indexCount; ++j)
        {
            if (stand > 0)
            {
                arr[1][j] -= minNum;
            }
            else
            {
                arr[1][j] += minNum;
            }
        }
 
        bool check = true;
        for (int i = 0; i < n; ++i)
        {
            if (arr[1][i] != 0)
            {
                check = false;
            }
        }
 
        if (check) break;
 
    }
 
    cout << answer;
}

 

최소한의 동작으로 전부 0으로 만들어야하는 문제이다.

그렇기 때문에 최우선순위로 같은 동작을 수행할 연속된 라인을 찾아야 한다.

타겟값에서 원본값을 빼서 어떤 동작을 수행해야할지 미리 구한다.

그리고 특정 인덱스를 기준으로, 뒤의 인덱스를 체크한다. 부호가 같으면 같은 동작을 수행할 수 있기 때문에 부호가 같다면 계속 탐색한다. 부호가 달라지는 순간, 연속된 라인이 아니라서 같은 동작을 수행할 수 없으니까 중지한다.

일단 어디까지가 연속된 라인인지 구했다면 몇칸이나 수행해야할지를 구해야 하는데, 연속된 값들 중 절대값이 가장 작은값을 적용해야 한다.

당연히 큰값으론 못한다. 이미 0이 되어서 완성되버린곳에 추가적으로 더하거나 빼면 안되기 때문이다.

절대값 작은걸 기준으로 각각 반영하고 다시 반복문 처음으로 돌아간다.

처음 뽑았던 인덱스부분의 값이 0이 되었다면, 즉 타겟으로 완성이 되었다면 다음 인덱스로 넘어가기위해 ++을 해주고 continue를 한다.

 

그러다가 값들이 전부 0이면 탈출한다. 사실 이러면 각 반복마다 최대 n번씩 검사해야해서 따로 값이 0이되는게 있을때마다 카운팅해서 n번되면 탈출하게 했는데... 로직상 뭔가 좀 특정케이스에서 값이 꼬이나보다.

해당문제 출제한곳으로 직접 가서 테스트케이스 다운받아서 전부 다 넣어봤는데 올바른 답이 나왔는데도, 백준에 제출하면 3%에서 out of bounds가 떠서 그냥 반복마다 전부 체크하는 코드로 대체하니까 바로 통과했다.

속도도 0ms라, 시간만 좀 날린 것 같다.