백준 2879번 코딩은 예쁘게

문제 링크입니다: https://www.acmicpc.net/problem/2879

분류는 스택과 다이나믹 프로그래밍이라고 되어있지만 단순 수학 문제로 접근했던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 현재 줄에 있는 탭의 개수와 원하는 탭의 개수의 차이를 diff 배열에 저장합니다.

2. 처음부터 끝까지 반복문을 통해 접근합니다.

i) 부호가 달라질 경우 더 이상 같은 그룹으로 못 묶으므로 무조건 이전의 차이(즉, diff[i-1])를 결과 값에 더해줍니다.

ii) 이전의 차이와 부호가 같고 양수일 떄는 증가수열(음수일 때는 감소수열)을 유지할 경우 같은 그룹으로 묶읍니다.

iii) 부호가 같더라도 증가수열(혹은 감소수열)을 유지 못하는 경우 또한 같은 그룹으로 묶지 못합니다.

-> 기존의 diff와 현재 diff 차이만큼을 결과 값에 더해줍니다.

3. 반복문이 끝나고 난 뒤, 남은 탭의 개수를 결과 값에 더해주고 결과를 출력합니다.

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 1000;

 

int N;

int before[MAX], diff[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> before[i];

 

        for (int i = 0; i < N; i++)

        {

                 int tab;

                 cin >> tab;

 

                 //기존 코드 인덴트와 차이

                 diff[i] = before[i] - tab;

        }

 

        if (N == 1)

                 cout << abs(diff[0]) << "\n";

        else

        {

                 int result = 0;

                 int prev = diff[0];

                 int cur = diff[0];

 

                 for (int i = 1; i < N; i++)

                 {

                         if (diff[i] >= 0)

                         {

                                 //부호가 다를 경우

                                 if (prev < 0)

                                 {

                                          result += abs(prev);

                                          prev = diff[i];

                                 }

                                 //오름차순

                                 else if (prev < diff[i])

                                          prev = diff[i];

                                 //오름차순이 끊겼을 경우

                                 else

                                 {

                                          result += abs(prev) - abs(diff[i]);

                                          prev = cur = diff[i];

                                 }

                         }

                         else

                         {

                                 //부호가 다를 경우

                                 if (prev > 0)

                                 {

                                          result += prev;

                                          prev = diff[i];

                                 }

                                 //내림차순

                                 else if (prev > diff[i])

                                          prev = diff[i];

                                 //내림차순이 끊겼을 경우

                                 else

                                 {

                                          result += abs(prev) - abs(diff[i]);

                                          prev = cur = diff[i];

                                 }

                         }

                 }

                 //마지막에 남아있는 탭

                 result += abs(prev);

                 cout << result << "\n";

        }

 

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~