-
1459. [Python]걷기Python_알고리즘/Silver IV 2023. 1. 25. 23:40
1. 문제
https://www.acmicpc.net/problem/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. 문제를 푸는데 도움이 되는 지식
- 그림을 통해서 직접 그려보는게 도움이 되는 것 같음
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1789. [Python]수들의 합 (0) 2023.01.30 11047. [Python]동전 0 (0) 2023.01.30 2217. [Python]로프 (0) 2023.01.29 11399. [Python]ATM (0) 2023.01.26 2839. [Python]설탕 배달 (0) 2023.01.23