백준알고리즘 14659번 한조서열정리하고옴ㅋㅋ C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 14659
• 문제명: 한조서열정리하고옴ㅋㅋ
• 언어: C#
• 분류: 그리디 알고리즘
• 비고: 

 

문제

“반갑다. 내 이름은 반고흐#31555! 조선 최고의 활잡이지. 오늘도 난 금강산 위에서 적들을 노리고 있지. 내 앞에 있는 적들이라면 누구도 놓치지 않아! 좋아, 이제 곧 월식이 시작되는군. 월식이 시작되면 용이 적들을 집어삼킬 것이다. 잘 봐두어라! 마장동 활잡이 반고흐#31555님의 실력을-!”

반고흐#31555는 자기 뒤쪽 봉우리에 덩기#3958이 있음을 전혀 모르고 있었다. 덩기#3958도 반고흐#31555와 마찬가지로 월식이 시작되면 용을 불러내어 눈앞에 있는 다른 활잡이들을 모두 처치할 생각이다. 사실, 반고흐#31555와 덩기#3958 뿐만 아니라 금강 산맥의 N개 봉우리에 있는 모든 활잡이들이 같은 생각을 가지고 있다.

반고흐#31555가 있는 금강 산맥에는 총 N개의 봉우리가 있고, 모든 봉우리마다 한 명의 활잡이가 서서 월식이 시작되기만을 기다리고 있다. 다만, 애석하게도, 천계에 맥도날드가 생겨 용들이 살이 찐 탓에 용들은 자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있게 되었다. 또한 용들은 처음 출발한 봉우리보다 높은 봉우리를 만나면 그대로 공격을 포기하고 금강산자락에 드러누워 낮잠을 청한다고 한다. 봉우리의 높이는 모두 다르고 모든 용들은 오른쪽으로만 나아가며, 중간에 방향을 틀거나, 봉우리가 무너지거나 솟아나는 경우는 없다.

“달에 마구니가 끼었구나.”

드디어 월식이 시작됐다! 과연 이들 활잡이 중 최고의 활잡이는 누구일까? 최고의 활잡이가 최대 몇 명의 적을 처치할 수 있는지 알아보자.

 

입력

첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 유일하다.

 

출력

최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력한다.

 

풀이

가장 오른쪽에 있는 활잡이는 아무것도 공격할 수 없다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 입력할 연산의 개수
int n = Convert.ToInt32(sr.ReadLine());
// 봉우리의 높이
int[] height = sr.ReadLine().Split().Select(int.Parse).ToArray();
// 처치할 수 있는 적의 최대 숫자
int maxKill = 0;
//  현재 처치한 적의 수
int kill = 0;
// 최고의 활잡이의 위치
int bestArcherPos = height[0];

// 활잡이의 공격, 가장 오른쪽에 있는 활잡이는 아무것도 공격할 수 없다.
for (int i = 1; i < n; i++)
{
    // 만약 현재 활잡이의 위치보다 다음 활잡이의 위치가 더 높다면
    if (height[i] > bestArcherPos)
    {
        // 이전 활잡이가 처치한 적보다 더 많은 적을 잡았다면
        if (kill > maxKill)
            // 최고 기록 경신
            maxKill = kill;
        // 최고 활잡이의 위치 변경
        bestArcherPos = height[i];
        // 새로운 최고 활잡이의 킬수 초기화
        kill = 0;
    }
    // 현재 활잡이의 위치보다 다음 활잡이의 위치가 더 낮거나 같으면
    else
        // 처치한다
        kill++;
}

// 이전 활잡이가 처치한 적보다 더 많은 적을 잡았다면
if (kill > maxKill)
    // 최고 기록 경신
    maxKill = kill;

// 처치할 수 있는 적의 최대 숫자 출력
sw.WriteLine(maxKill); ;

sw.Flush();
sr.Close();
sw.Close();

 

후기

이것도 피드백을 받아서 풀었다. 피드백 이전에도 겉으로 보면 정답이 나오는 코드가 있어서 같이 올리겠다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 입력할 연산의 개수
int n = Convert.ToInt32(sr.ReadLine());
// 봉우리의 높이
int[] height = new int[n];
// 봉우리의 높이 입력
height = sr.ReadLine().Split().Select(int.Parse).ToArray();
// 최고의 활잡이
int bestArcher = 0;
// 최고의 활잡이의 위치
int bestArcherPos = 0;
// 처치할 수 있는 적의 최대 숫자
int maxKill = 0;

// 활잡이는 자기 앞에 있는 활잡이만 공격할 수 있다.
for (int i = 0; i < height.Length - 1; i++)
{
    bestArcherPos = Math.Max(bestArcherPos, height[i]);
}

// 활잡이의 정확한 위치 탐색
for (int i = 0; i < height.Length; i++)
    if (bestArcherPos == height[i])
        bestArcher = i;

// 활잡이는 자기가 서 있는 봉우리에 있는 적만 처치할 수 있다
for (int i = bestArcher; i < height.Length; i++)
    if (height[bestArcher] > height[i])
        maxKill++;

// 처치할 수 있는 적의 최대 숫자 출력
sw.WriteLine(maxKill);

sr.Close();
sw.Close();

 

위쪽 코드와 다르게 반복문을 3개 사용했다. 물론 반복문 안에 반복문은 아니고 독립된 형태로 3번 돌렸다는 것이다. 첫 번째 반복문은 최고의 활잡이의 위치를 파악하는 것이고 두 번째 반복문은 활잡이의 0부터 n - 1로 표기된 정확한 위치를 찾는 것이고 세 번째 반복문은 활잡이가 자신보다 더 낮은 곳에 있는 적을 처치하는 것이었다. 참고로 for문에서 소스 코드를 한 줄만 사용해도 중괄호를 지우면 컴파일 에러가 나니 지우지 말고 그냥 두어야 한다. 겉으로 보면 정답이지만 실상은 오답인 코드도 있었다...

그래서 백준 알고리즘의 질문 게시판마다 반례 요청이 쏟아지는 것 같다.