[SWEA]D2_1859_백만장자프로젝트

SW Expert Academy

---

🚨 내가 잘못생각했던 부분

처음 생각 : 앞에서 부터 검사하면서 그 전값보다 크면 max_v에 넣고 작으면 처음부터 max_v까지 계산

시작지점을 max_v+1(그 전값보다 작았던 위치)로 바꾸고 반복

 

잘못된 이유 : '11312' 같은 경우는 이 생각이 성립하지만 그 뒤에 더 큰 최대값이 나올 경우 성립하지 않는다. 예를 들면,

'11321623'의 경우에 처음 생각대로라면 3, 2, 6, 3에서 검사를 했겠지만 실제로는 6, 3에서만 계산해야한다. 따라서 전체의 최대값을 찾는 것을 먼저 해야한다.

 

더 나아가서 : 이런 경우에는 뒤에서 부터 검사하는 것이 좋다. 아직 그 이유를 정확하게 설명하지는 못하겠다..^^

---

파이썬 보충반을 신청하고 처음으로 파이참에서 파이썬으로 알고리즘 문제를 풀었다.

이 문제는 영광의 첫 문제!

 

T = int(input())
for tc in (1, T+1):
    N = int(input())
    # type적고 입력받은거 띄어쓰기로 나눠서 list에 저장
    costs = list(map(int, input().split()))
    result = 0

    # 최대값 찾기
    max_i = 0
    max_v = costs[max_i]
    idx = max_i
    while idx < N:
        max_i = idx
        max_v = costs[max_i]

        # 최대 값을 찾는 반복문
        for i in range(idx, N):
            # 현재 인덱스의 값이 최대 값보다 클 때
            if costs[i] >= max_v:
                # 최대값과 최대값의 인덱스 갱신
                max_v = costs[i]
                max_i = i
        # 위에서 구한 최대값으로 계산
        for i in range(idx, max_i):
            result += (max_v-costs[i])
        idx = max_i + 1

    print(result)

 

잘못생각했던 부분만 잘 파악하면 쉬운 문제이다.

다음에는 이런 문제를 쉽게 풀 수 있는 방법인 뒤에서 부터 최댓값을 찾는 방법으로 풀어봐야겠다.