LG 코딩테스트 예제 - 마리오 게임

LG 공고를 보다가 코딩테스트 예제를 보고 한번 풀어보았다.

 

많은 예시들이 있는 것이 아니라 이게 정답이라고 할 수는 없지만 일단 내 생각에 이게 맞는 것도 같고.. 반례를 찾아보려 노력했는데 찾기 힘들어서 끄적일겸 기록할겸 포스팅!!

 

[요구사항]
마리오게임은버섯을규칙에맞게먹어서키를최대한키우는단순한게임으로가장키를많이키운사람이우승이다.
값범위
1. 버섯의개수N (N=자연수, 1≤N≤150,000)
2. 버섯은일렬로늘어져있으며0번부터N-1번까지있음
3. 버섯에써있는숫자P (P=자연수, 1≤P≤500)

버섯을먹는규칙
1. 버섯은0번부터순서대로먹을지먹지않을지결정해야함
2. 첫번째로먹은버섯의숫자만큼키가커짐
3. 두번째로먹은버섯의숫자만큼키가작아짐
4. 즉, 홀수번째로먹은버섯의숫자만큼커지고짝수번째로먹은숫자만큼작아짐

 

 

공식 홈페이지에서 공개되어있는 자료임!!

 

여기서 수학적으로 접근을 해서 규칙을 찾으려고 해보았는데 꽤나 까다로웠기 때문에 단순하게 생각하기로 했다.

 

지금 값과 다음 값을 비교해서 홀수번째에서는 큰 값을 더해주고 짝수번째에서는 작은 값을 빼주면 된다고 생각했다.

 

어차피 계속해서 한칸한칸 이동하며 비교하기 때문에 앞뒤의 값을 계속 비교할 수 있게 된다. 

 

홀수번째에는 최대한 큰 값을 더하려고 할 것이고 짝수번째에는 최대한 작은 값을 빼려고 할 것이기 때문에 결국 최대값을 도출해낼 수 있지 않을까? 라는 아이디어에서 시작했다. 솔직히 잘 안될 것이라고 생각했지만 의외로 결과값이 좋았다.

 

import sys
input = sys.stdin.readline

n = int(input()) # 8
lst = list(map(int, input().split())) # 7 2 1 8 4 3 5 6


def fun(n, lst):
    answer = 0
    k = 1
    for i in range(n):
        if i != n-1:
            if k%2 != 0:
                if lst[i] >= lst[i+1]:
                    answer += lst[i]
                    k += 1
                else:
                    pass
            else:
                if lst[i] <= lst[i+1]:
                    answer -= lst[i]
                    k += 1
                else:
                    pass
        else:
            if k % 2 != 0:
                answer += lst[i]
                k += 1
    return answer

print(fun(n, lst))

 

 

 

PDF에서 제공한 예제. 잘 해결됨

 

중복의 경우에도 잘 해결됨

 

 

이것 이외에도 굉장히 여러개 친구와 함께 반례를 찾아보려했는데

 

찾지 못했다. 

 

좀 더 다양한 예시와 답안이 있었으면 좋았지 않았을까 하는 아쉬움이 남지만..

 

 

 

LG코테 문제를 보며 가장 어려운 건 문제도 아니고 입출력방식인듯하다.

 

프로그래머스랑 다르게 입출력을 내가 셋팅해야된다는 점이 익숙하지 않아서인지 어색하다.