https://codeforces.com/contest/1529/problem/A
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 100)
- n m k (1 ≤ n,m ≤ 100; 0 ≤ k ≤ 104)
output :
- For each test case, if you can reach cell (n,m) spending exactly k burles, print YES. Otherwise, print NO.
각 테스트 케이스에서 (n, m)위치를k에 도착할 수 있다면 "YES"를 그렇지 않으면 "NO"를 출력하시오.
조건 :
- You can move to the neighboring cells to the right or down. In other words, suppose you are standing at cell (x,y). You can:
move right to the cell (x,y+1) — it costs x burles;
move down to the cell (x+1,y) — it costs y burles.
인접한 위치로 오른쪽 혹은 아래로 이동 할 수 있다. 다시 말해 (x, y)에서 (x, y + 1)로 이동하는 경우 x가 발생하고 (x + 1, y)로 이동하는 경우 y를 사용한다.
BFS와 비슷하게 각 위치에서 아래, 오른쪽으로 이동하면서 자기 현재 위치에서의 값을 더해주면 된다.
풀이에서는 넓이를 구해서 1을 빼는데 .....
시그마를 이용하느 것도 아니고 그냥 곱셈을 사용한다.. 물론 규칙을 찾을 수야 있는데 일단 뭐 그렇다.
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n, m, k = map(int, sys.stdin.readline().split())
ans = [[float('INF')] * (m + 1) for i in range(n + 1)]
ans[1][1] = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if i < n:
ans[i + 1][j] = min(ans[i + 1][j], j + ans[i][j])
if j < m:
ans[i][j + 1] = min(ans[i][j + 1], i + ans[i][j])
print("YES" if ans[-1][-1] == k else "NO")
