Educational Codeforces Round 108 (Div. 2) 참가 후기
처음으로 Div. 2에서 2솔브를 해냈다. 그런데 A, B문제는 너무 쉬웠다. C도 풀 수 있었는데 아쉽다.
A. Red and Blue Beans
를 1개 이상의 packets으로 나누어 담을 수 있는지 확인하는 문제다. 각각 1개 이상은 담아야 하고 를 만족해야 한다.
우선 입력의 크기를 보자마자 직접 해보는 것은 아니고 수식으로 나타내는 방법이 있겠구나 생각하였다. (그런데 입력이 이렇게 큰데 처음에 int 자료형 사용해서 한 번 틀렸다)
담을 수 있는지 여부만 확인하면 되니까 최대한 packet을 많이 만들면 더 많이 담을 수 있을 것이다. 어느쪽이건 더 적은 쪽의 개수만큼(여기서는 라고 하자) packet을 만들면 packet에 는 필연적으로 한 개씩 밖에 못 들어간다. 조건을 만족하면서 최대한 넣을 수 있는 의 개수는 이 된다.
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
의 배열의 에서 으로 정확히 비용만을 소모해서 도달하고자 한다. 에서 오른쪽으로 한 칸 이동하면 행의 인덱스 만큼 비용을 소모하고, 아래로 한 칸 이동하면 열의 인덱스 만큼 비용을 소모한다.
처음엔 과 의 크기 제한을 보고 DP로 접근을 시도했다. 그런데 그렇게 되면 지금까지 소모한 비용이 DP함수의 인자로 필요한데, 당연히 가 되어서 배열 할당만으로 메모리 초과다.
그러면 혹시 까지 오는데 든 비용을 수식으로 알아낼 수 있는 건가? 라는 생각이 들어서 직접 몇번 그리면서 해봤는데 어떤 방식으로 에 도착했건 간에 비용이 일정한 것을 알았다. 그런데 이러면 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");
}
}
}
Author And Source
이 문제에 관하여(Educational Codeforces Round 108 (Div. 2) 참가 후기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@axiom0510/Educational-Codeforces-Round-108-Div.-2-참가-후기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)