[ Codeforces - Codeforces Round #802 (Div. 2) (06/24) ] - #A Optimal Path(Python)

• 문제링크

https://codeforces.com/contest/1700/problem/A

Problem - A - Codeforces

 

 

 

• 문제

 

 

• 시행착오

큰 시행착오는 없었지만, 계산실수가 있었다.

 

 

 

• 문제분석

행이 n개, 열이 m개 존재하는 테이블은 가장 왼쪽 최상단이 1로 시작하고 오른쪽으로 갈때마다 1씩증가하며, 밑으로갈때마다 m씩 증가하는 비용을 가진다. 테스트케이스 t와 행열 n,m이 주어졌을때 왼쪽최상단(1)에서 n,m좌표까지 도착할때 가장 최소의 비용을 출력하는 문제이다.

 

 

 

• 각 파라미터의 유형

t = 3

< 조건 >  1 ≤ t ≤ 1000 

=> 숫자로 이루어진 반복할 횟수이다

 

n,m

< 조건 >  1 ≤ n,m ≤ 10^4

=> 숫자로 이루어진 행과 열이다.

 

 

 

• 문제접근

※ 작성자가 문제를 보고 든 생각을 차례대로 써본 것이다. 이 순번은 정답이 아니며 매번 다른 생각을 해보길 권장한다.

1)  어떻게 최소의 비용으로 목적지에 도착할 수 있는지 "n과 m이 같을때 / m보다 n이 클 때 / n보다 m이 클 때"로 케이스를 나눠 임의의 숫자를 넣어 대입해 실제로 값을 구해보았다.

=> n=2, m=2 일 경우, 1 → 2 → 4 로 7이었다.

=> n=2, m=3 일 경우, 1 → 2 → 3 → 6 로 12였다. 

=> n=3, m=2 일 경우, 1 → 2 → 4 → 6 로 13이었다.

이를 통해, ㄱ 자 방향으로 가는 것이 최단거리임을 알게되었다.

 

2) 어떤 경로가 최단거리인지를 알았으니, 계산하는 방법에 대해 생각했다. 1~N까지의 합은 N*(N+1)/2이므로 ㄱ으로 갈때 ㅡ 진행의 끝까지의 총 합은 m*(m+1)/2임을 알수 있 다. 이제 ㅣ진행에 대해 생각해야 하는데 M~N*M이므로 1~M까지의 합에 N을 곱하면 이를 얻을 수 있으므로,  N*M*(M+1)/2임을 알 수 있다.

여기서 ㅡ의 끝과 l의 시작점이 겹치므로 이를 빼줘야하는데 값은 M이다.

최종적으로는 밑의 식이 나온다

 

 

• 최종코드

for i in range(int(input())):
    n,m=map(int, input().split())
    print(int(m*(m+1)/2+m*n*(n+1)/2-m))