[Silver I] 건공펀치 등차수열 - 30825

문제 링크

성능 요약

메모리: 138904 KB, 시간: 136 ms

분류

수학, 그리디 알고리즘

제출 일자

2025년 8월 31일 11:45:01

문제 설명

서울시립대학교의 마스코트와도 같은 존재인 건공이는 어떤 수열을 주더라도 공차가 $K$인 등차수열로 만들어 버리는 버릇이 있다.

건공이는 주어진 수열을 등차수열로 만들기 위해, 건공펀치를 1회 사용하여 수열의 한 원소의 값을 1 증가시킬 수 있다.

건공이는 건공펀치를 최소로 사용하고 싶어하지만, 수열의 길이가 너무 길어 건공펀치의 최소 사용 횟수를 구하는 데 어려움을 겪고 있다.

건공이를 대신하여 주어진 수열을 등차수열로 만드는 데 필요한 건공펀치의 최소 사용 횟수를 구해보자.

입력

첫 번째 줄에 수열의 길이 $N$과 공차 $K$가 공백으로 구분되어 주어진다. ($2 \le N \le 200\ 000$, $1 \le K \le 200\ 000$)

두 번째 줄에 수열 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 100\ 000$)

출력

주어진 수열을 공차가 $K$인 등차수열로 만드는 데 필요한 건공펀치의 최소 사용 횟수를 출력한다.

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/30825
 
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
 
ans = 0
 
for i in range(len(a_list) - 1):
    # print(a_list)
    #현재 vs 이후의 값 비교 > k가 아니면 조정 하는 식으로
    if a_list[i + 1] - a_list[i]  != k:#공차수열 아닌 경우
        
        if (a_list[i + 1] - a_list[i]) < k:#이후의 값 조정
            
            
            ans += (a_list[i] + k) - a_list[i + 1]
            # print(ans)
            a_list[i + 1] = a_list[i] + k
            
            
        elif a_list[i + 1] - a_list[i] > k:#현재의 값 조정
            temp_ans = (a_list[i + 1] - a_list[i]) - k
            ans += temp_ans
            # print(ans, '!')
            a_list[i] = a_list[i + 1] - k
            #i가 현재, 0 ~ i-1 까지 tempans만큼 증가시키자
            for i2 in range(0, i -1 + 1):
                a_list[i2] += temp_ans
                ans += temp_ans
                # print(ans, '!!')
                
        else:
            print("예외 경우 발생")
 
        
# print(a_list)
 
print(ans)
 
 
##현재의 것을 증가시키는 방식은
#다음 것을 증가 시키는 케이스와 충돌
 
##그냥 뒤에서부터 시작하는건?< 똑같을듯;
 
#또틀림;