백준 11924번 PIANINO

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

상대적 높이차가 핵심이였던 문제였습니다.

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

1. 상대적 높이차를 구해주는데 이전 높이에서 (현재 높이차의 부호)만큼 더해줍니다.

2. 상대적 높이차가 같은 키 중에 첫 번째 키와 동일하다면 무조건 누르므로 result를 증가시킵니다.

3. 상대적 높이차가 다를 경우 (현재 키와 첫 번째 키의 차)가 상대적 높이에 나누어 떨어지고 해당 몫이 음수가 아닐 경우에 map을 통해 몫이 몇번 등장했는지 표시해줍니다.(몫 = 잠재적 K)

4. map을 순회하면서 제일 많이 등장한 몫이 K이고 (해당 K가 등장한 횟수 + 2번에서 구한 result)가 맞게 눌린 횟수입니다.

#include <iostream>

#include <algorithm>

#include <map>

using namespace std;

 

const int MAX = 1000000;

 

int key[MAX], diff[MAX];

map<int, int> m;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

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

                 cin >> key[i];

 

        //높낮이

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

        {

                 //높이차가 있는 경우

                 if (key[i] - key[i - 1])

                         diff[i] = diff[i - 1] + (key[i] - key[i - 1]) / (abs(key[i] - key[i - 1]));

                 //없는 경우

                 else

                         diff[i] = diff[i - 1];

        }

 

        int result = 0;

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

        {

                 if (!diff[i])

                 {

                         //같은 키

                         if (key[i] == key[0])

                                 result++;

                 }

                 else

                 {

                         //나누어 떨어지고 몫이 음수가 아닐 경우

                         if (((key[i] - key[0]) % diff[i]) == 0 && ((key[i] - key[0]) / diff[i]) >= 0)

                                 m[(key[i] - key[0]) / diff[i]] += 1;

                 }

        }

 

        int K = 0, cnt = 0;

        for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++)

        {

                 if (iter->second >= cnt)

                 {

                         K = iter->first;

                         cnt = iter->second;

                 }

        }

 

        cout << result + cnt << "\n";

        cout << K << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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