[Greedy] 백준 - 2879번 코딩은 이쁘게

백준 - 2879번 코딩은 이쁘게

😊 문제 요약

코드 편집을 하기 위해서는 다음과 같은 과정이 필요하다.

1.연속된 줄을 그룹으로 선택한다.
2.선택된 줄의 앞에 탭 1개를 추가하거나 삭제한다.

다음과 같은 과정이 하나의 편집이며 편집횟수의 최소로 하여 올바른 편집(x(기존) = y(올바른))을 하도록 하여라.

😘 key point

사실은 그리디의 문제이지만 직관적인 느낌이 오지 않아 브루트 포스적인 방법을 실행하였다.

연속인지 확인하기 위해서는 바로 옆 항과의 비교가 필요하다. 따라서 x,y옆에 0을 추가로 넣어주어 모든 항이 연속적인지 확인한다. 그래고 대소 관계를 비교하는 make_z함수를 만들어 y값이 크면 1, 작으면 -1, 그리고 같으면 0을 만들었다.

다음과 같은 구조에서 코드를 보면 좀 더 이해가 쉬울 것이다.

🎂 코드

n = int(input())

#윗줄 
x = list(map(int, input().split())) 

#아랫줄
y = list(map(int, input().split())) 

#연속 비교를 위해 0을 추가
x.append(0)
y.append(0)

#x항, y항 대소 비교 
def make_z(k):
    if y[k] > x[k]:
        return 1
    elif y[k] < x[k]:
        return -1

    else:
        return 0        

cnt = 0

while x !=y :
    for i in range(len(x)-1):
        if make_z(i) == 0:
                continue
        
        #연속인지 확인하기 위해서는 바로 옆의 항만 알면 해결할 수 있다. 
        if make_z(i) == make_z(i+1):
            
            #한 칸씩 점점 x = y 같아지게 해준다. 
            if make_z(i) == 1:
                x[i] += 1
            
            elif make_z(i) == -1:
                x[i] -= 1

        else:
            
            #연속이 아니면 cnt추가
            cnt += 1

            #한 칸씩 점점 x = y 같아지게 해준다. 
            if make_z(i) == 1:
                x[i] += 1

            elif make_z(i) == -1:
                x[i] -= 1

print(cnt)