오늘의 키워드
•
수학적 규칙
•
조건 분기
•
최적화
문제 파악 및 풀이
•
문제를 처음 봤을 때 최대 숫자가 매우 커서 그리디 알고리즘을 생각했다.
•
하지만 문제를 자세히 분석해보니, N과 M의 크기에 따라 경우를 나눠 수학적으로 해결할 수 있는 문제였다.
•
이동 방법이 제한적이기 때문에, 세로 길이(N)와 가로 길이(M)에 따라 이동 횟수가 수학적으로 결정된다.
•
다만, 코드를 깔끔하게 작성하지 않아 조건별 경우를 찾는 데 시간이 걸렸다.
핵심 아이디어
•
세로(N)가 3 이상이고 가로(M)이 6 이상이면 다양한 이동이 가능하여 (M - 2)가 최대 방문 칸 수가 된다.
•
세로가 2인 경우에는 이동에 제약이 많아 (M - 1) / 2 + 1로 계산된다.
•
세로가 1인 경우에는 이동이 불가능하여 방문 가능한 칸 수는 항상 1이다.
Java 풀이
import java.io.*;
import java.util.*;
class Main {
public static final int MAX_N = 2000000000;
public static int n, m;
public static int ans = 1;
public static void main(String[] args) throws IOException {
init();
if (n >= 3) {
if (m >= 6) {
ans = m - 2;
} else {
ans = Math.min(4, m);
}
} else if (n == 2) {
ans = Math.min(4, (m - 1) / 2 + 1);
}
System.out.println(ans);
}
public static void init() throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
}
}
Java
복사
시간 복잡도
•
O(1)
단순히 입력을 받고 조건 분기만 수행하기 때문에, 전체 시간 복잡도는 O(1) 이다.
오늘의 회고
어려웠던 점
•
문제를 보고 수학적 접근을 바로 하지 못하고 처음에는 그리디를 떠올렸다.
•
조건 분기 코드가 깔끔하지 않아 각 경우를 확인하고 디버깅하는 데 시간이 오래 걸렸다.
개선점
•
문제를 풀 때 입력 범위와 이동 제한 조건을 정확히 분석하고, 단순 수학적 규칙으로 해결할 수 있는지 빠르게 판단하는 연습이 필요하다.
•
깔끔한 조건 분기를 작성하는 습관을 들여, 실수를 줄이고 디버깅 시간을 단축해야겠다.