[백준/C++/USACO] 23879번 Air Cownditioning 풀이

문제 이해

---

---

문제 풀이

---

이 문제에서 주어지는 배열 2개의 차이를 가지고 이리저리 그리디하게 생각해보았지만 도저히 패턴을 찾을 수 없었고
조금 신박한 방법으로 풀어야하는 문제였다.

 

문제에서 주어준 배열의 차이는 아래와 같은데 이 이후로가 생각하지 못했던 신박한 부분이었다.

원래 온도와 희망 온도의 차이 배열

인접한 차이들의 차이 (빨간색이 추가한 0이다)

여기에 앞뒤로 0을 붙여주고 인접한 두 수 사이의 차를 구하면 이렇게 되는데

 

[증명]

basis: 어떤 값이 0에서 시작해서 0이 되려면 더하고 뺀 값이 같아야하는 것은 자명하다.

 

우리가 원하는 것은 결국 희망 온도의 차이가 0이 되는 것이고

희망 온도의 차이가 0이 되면 인접한 차이 값 역시 0이 되어야 한다.

 

빨간색이 변경한 구간과 바뀐 값이다.

특정 구간의 배열에 1도를 높이거나 1도를 낮추면 위 그림처럼

선택한 배열 앞 뒤로 +1과 -1 혹은 -1 +1 되는 것을 확인할 수 있다.
(값을 1올리거나 1내리거나 하면 올라가지 않은 인접값이 +-1 되는 것은 당연하다)

 

그렇다면 최소 실행 횟수는 배열의 구간을 임의로 선택하여 인접한 차이

양수를 모두 0으로 혹은 음수를 모두 0으로 만들어주는 횟수와 같다.

 

고로 모든 양수만 더하거나 음수만 더한 값이 정답이 된다.
아래 코드에서는 절대값으로 모두 더하고 나누기 2를 해주었다.

---

코    드

---

#include <bits/stdc++.h>
using namespace std ;

int main()
{
    int N, answer = 0 ;
    cin >> N ;
    
    vector<int> temp(N+2) ;
    for(int i = 1 ; i <= N ; i++)
        cin >> temp[i] ;
    
    for(int i = 1 ; i <= N ; i++)
    {
        int want ;
        cin >> want ;
        temp[i] -= want ;
    }

    for(int i = 0 ; i <= N ; i++)
        answer += abs(temp[i] - temp[i+1]) ;
    
    cout << answer / 2 << "\n" ;
}

---

느낀점: 매번 느끼지만 그리디가 제일 어렵다. 아이큐테스트 하는데 지능이 모자란 느낌이다.

문제점: https://www.acmicpc.net/problem/23879

23879번: Air Cownditioning