Educational Codeforces Round 108 (Div. 2) 참가 후기

Educational Codeforces Round 108 (Div. 2)

처음으로 Div. 2에서 2솔브를 해냈다. 그런데 A, B문제는 너무 쉬웠다. C도 풀 수 있었는데 아쉽다.

A. Red and Blue Beans

$(r,\ b)$를 1개 이상의 packets으로 나누어 담을 수 있는지 확인하는 문제다. $r_i,\ b_i$ 각각 1개 이상은 담아야 하고 $|r_i−b_i|≤d$를 만족해야 한다.
우선 입력의 크기를 보자마자 직접 해보는 것은 아니고 수식으로 나타내는 방법이 있겠구나 생각하였다. (그런데 입력이 이렇게 큰데 처음에 int 자료형 사용해서 한 번 틀렸다)
담을 수 있는지 여부만 확인하면 되니까 최대한 packet을 많이 만들면 더 많이 담을 수 있을 것이다.$r,\ b$ 어느쪽이건 더 적은 쪽의 개수만큼(여기서는 $r \ge b$라고 하자) packet을 만들면 packet에 $b$는 필연적으로 한 개씩 밖에 못 들어간다. $|r_i−b_i|≤d$ 조건을 만족하면서 최대한 넣을 수 있는 $r$의 개수는 $b \times (d + 1)$이 된다.

public class A {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			long r = Integer.parseInt(st.nextToken());
			long b = Integer.parseInt(st.nextToken());
			long d = Integer.parseInt(st.nextToken());
			if (r < b) {long temp = r; r = b; b = temp;}
			System.out.println(b * (d + 1) >= r ? "YES" : "NO");
		}
	}
	
}

B. The Cake Is a Lie

$n×m$의 배열의 $(1,\ 1)$에서 $(n,\ m)$으로 정확히 $k$비용만을 소모해서 도달하고자 한다. $(y, \ x)$에서 오른쪽으로 한 칸 이동하면 행의 인덱스 만큼 비용을 소모하고, 아래로 한 칸 이동하면 열의 인덱스 만큼 비용을 소모한다.
처음엔 $n$과 $m$의 크기 제한을 보고 DP로 접근을 시도했다. 그런데 그렇게 되면 지금까지 소모한 비용이 DP함수의 인자로 필요한데, 당연히 $O(100\times 100\times 10^4)$가 되어서 배열 할당만으로 메모리 초과다.
그러면 혹시 $(y,\ x)$까지 오는데 든 비용을 수식으로 알아낼 수 있는 건가? 라는 생각이 들어서 직접 몇번 그리면서 해봤는데 어떤 방식으로 $(y,\ x)$에 도착했건 간에 비용이 일정한 것을 알았다. 그런데 이러면 DP로 풀 필요가 없구나 깨달아서 바로 수식으로 끝냈다.

public class B {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());		
			System.out.println(N - 1 + (M - 1) * N == K ? "YES" : "NO");
		}
	}
	
}