백준_곰곰아 선 넘지마_26075(python)

※ 접근법

 n,m을 더했을 때 문자열의 최대 길이는 십만이고 s와t가 주어진다. 0과 1의 조합이 어떻게 이루어졌을 때 s와 t가 가장 적게 이동해서 값을 만들어낼까?..... 시간제한은 1초 떠오르는 것은 그리디 알고리즘 밖에 없었다. 그렇다면 이것을 어떻게 그리디하게 풀까? 

 처음 떠올렸던 것은 그냥 간단하게 1을 기준으로 더 적게 움직이는 쪽에서 상대방에게 1을 맞추자였다. 이렇게 하니 최소가 아니었다. 여기서!!! 멘붕에 빠져서 헤매다가 결국 친구에게 힌트를 물어봤고 친구는 거리를 좁힌다는 생각을 해보라고 했다.

 

★ 풀이

1. s,t의 1의 좌표를 새로운 s_data, t_data에 저장한다.

2. 순서대로 하나씩 꺼내 둘의 차이를 구해서 answer에 계속 더한다.

3. answer을 홀수,짝수 여부를 구분해서 반 씩 나눠가져서 결과값에 더하면 된다.

문제는 최솟값만 구하면 된다. s와 t중 어느 텍스트가 몇 번을 움직였는지는 궁금하지 않다. 그렇다면 3번만으로 답이 어떻게 입증되는 것일까 그것은 구하는 과정에 의해서 결과가 입증되는 것이다.

필자는 1의 사이를 좁혀서 값을 구했다. 즉 s와 t의 가장 가까운 1의 거리 차이가 짝수 였다면 둘은 거리 차이의 반 씩 이동했을 것이고 홀수였다면 둘은 거리차이의 반에서 한번 더 움직였을 것이다. 근데 이것은 s가 한번 더 움직였어도 됐고 t가 한번 더 움직였어도 됐다. 여기서 중요한 것은 두 곰곰이는 거리 차이의 반씩 계속 움직였다는 것이다.  

 

★ 코드블럭

n,m = map(int,input().split())
s = list(input())
t = list(input())
snum = tnum = 0
s_data = []
t_data = []
for num in range(len(s)):
    if s[num] == '1':
        s_data.append(num)
    if t[num] == '1':
        t_data.append(num)

answer = 0
for i in range(len(s_data)):
    answer += abs(s_data[i] - t_data[i])
re = 0
if answer % 2 == 0:
    re = (answer // 2) ** 2 * 2
else:
    re = (answer // 2) ** 2
    re += (answer // 2 + 1) ** 2
print(re)

★ 회고록

 그리디 알고리즘인것을 안 순간 직관적으로 문제를 풀려고 시도했다. 하지만 매번 그리디 알고리즘은 단순하게 풀려고 시도하면서도 단순하게 생각하지 않으려고 한다. 내가 쓰면서도 무슨 말인지 모르겠다. 단순하다의 개념이 추상적이라서 모호한 것 같다. 어느 기준까지가 단순한 것인지 근데 항상 그리디 문제를 풀고나면 단순하다는 생각이 먼저 떠오른다. 그렇다면 이 단순한 것을 왜 떠올리지 못하는 것일까? 너무 쉽게 생각해서인 것 같다. 티어에 대한 존중을 해줘야하는데 그리디인 것을 보면 그냥 단순 직관적으로 풀려고 한다. 이 문제에서도 1을 상대방에게 맞춘다는 것을 떠올리고 최소가 아닌 것을 알았다면 둘의 사이를 좁혀본다는 생각은 떠올릴만 했는데 그렇지 못했다. 그냥 저기서 멘붕에 빠졌다. (이게 아니라고?) 한 번 이렇게 고뇌에 빠지면 혼자 상상의 나래를 펼친다. 보통의 경우 처음 떠올린 방법이 너무 어긋나지만 않았다면 틀을 벗어나지 않는 것 같다. 이 느낌을 잊지말고 계속 기억해보자