1459. [Python]걷기

1. 문제

 

https://www.acmicpc.net/problem/1459

1459번: 걷기

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 경우의 수 생각

 

3. 파이썬 코드

 

X,Y,W,S = map(int,input().split())

# 직선으로 이동한 거리
s1 = (X+Y)*W

# 대각선으로만 이동한 거리 X,Y의 합이 2의 배수가 아닌경우 홀수로 한칸이 남기때문에 조건을 다르게 해줘야한다.
if (X+Y) % 2 == 0:
    s2 = max(X,Y)*S
else:
# 대각선 이동 + 한칸 이동거리
    s2 = (max(X,Y)-1)*S + W

# 대각선 최대이동 + 나머지 블록이동
s3 = (min(X,Y)*S + (max(X,Y)-min(X,Y))*W)

print(min(s1,s2,s3))

 

4. 문제를 풀고난 후 생각

 

• 문제를 읽고 대각선을 이동하는 방법과 직선을 이동하는 방식 두개의 방법만 있다고 생각을 하고 구현을 진행했었다.
• 하지만 채점을 돌렸을때 틀렸고 예제 문제들을 살펴보며 어떠한 경우에서 최소의 값이 나오는지 규칙에 대해서 생각을 해봤다.

• 위의 그림과 같은 세가지 경우의 수가 존재하며 W(직선 블록 이동시 소요되는 거리), S(대각선 이동시 소요되는 거리)에 따라서 이 경우값들에서 최소값을 출력하는 것이 문제에서 원하는 답이라는 것을 알게되었다.
• 두 경로의 합에서 홀수가 되는경우 모두 대각선으로 움직일 수 없고 한칸 블록전진하고 대각선으로 움직일 수 있는 것도 예제 문제를 넣어보며 알게되었고 (홀 + 홀 = 짝 , 홀 + 짝 = 홀 , 짝 + 짝 = 짝) 이므로 X,Y의 합이 홀수일 경우랑 짝수인 경우를 나눠서 s2를 따로 구하는 식을 넣었다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 그림을 통해서 직접 그려보는게 도움이 되는 것 같음