Hikenny25
2일차 - Ladder2 본문
def line_to_line_distance(start, end):
return abs(start_column[start]-start_column[end]) - 1
array_size = 100
repeat_number = 10
ans = list()
for _ in range(repeat_number):
_ = input()
ladder = [list(map(int, input().split())) for _ in range(array_size)]
start_column = list()
for i in range(array_size):
if ladder[0][i] == 1:
start_column.append(i)
distance = list()
for i in range(len(start_column)):
ladder_cnt = i
temp_dist = 0
change_cnt = 0
r, c = 0, start_column[i]
for j in range(array_size - 1):
r += 1
if c > 0 and ladder[r][c-1] == 1: # 좌측 경로
ladder_cnt -= 1
c = start_column[ladder_cnt]
temp_dist += line_to_line_distance(ladder_cnt + 1, ladder_cnt)
change_cnt += 1
elif c < array_size - 1 and ladder[r][c+1] == 1: # 우측 경로
ladder_cnt += 1
c = start_column[ladder_cnt]
temp_dist += line_to_line_distance(ladder_cnt - 1, ladder_cnt)
change_cnt += 1
else:
c = c
distance.append(temp_dist + change_cnt)
min_dist = 1e12
min_idx = 0
for i in range(len(distance)):
if distance[i] <= min_dist:
min_dist = distance[i]
min_idx = start_column[i]
ans.append(min_idx)
for i in range(repeat_number):
print(f"#{i+1} {ans[i]}")
경로를 따라 가는 방식은 Ladder1 문제와 동일하다!
그러나 이 경우에는 모든 경로의 거리를 구하고 비교해주어야 해서 연산 횟수가 더 증가한다...
거리를 구한 방식은 내려가는 1의 갯수는 똑같기 때문에 제외하고, 좌측/우측 경로로 이동할 때마다 change_cnt에는 1씩, temp_dist에는 그 사이의 거리를 더해주었다...
고려해야할 점은 거리가 2인 직선 사이를 한 번 움직이는 것과 거리가 1인 직선 사이를 두 번 움직이는 것의 거리가 다르다는 것이다.. 따라서 change_cnt 변수를 만들어 해결해주었다!
'SW Expert Academy > Programming - Intermediate' 카테고리의 다른 글
5일차 - 배열 최소 합 (0) | 2023.12.12 |
---|---|
5일차 - 토너먼트 카드게임 (1) | 2023.12.12 |
2일차 - Ladder1 (1) | 2023.12.11 |
2일차 - Sum (1) | 2023.12.11 |
1일차 - Flatten (0) | 2023.12.11 |
Comments