[99클럽 코테 스터디] 99클럽 코테 스터디 10일차 TIL + 탐욕법

1. 오늘의 학습 키워드

• 탐욕법
• 문제 URL : https://www.acmicpc.net/problem/1783

2. 공부한 내용 본인의 언어로 정리하기

• 시도1(틀림)
  • 접근 방법
    • 경우의 수를 전부 탐색해서 최대값을 찾아야 하는 문제인가 싶어 DFS 알고리즘을 떠올렸다.
  • 문제점
    • DFS는 모든 경로를 탐색하므로 이동 횟수가 많아질 경우 시간 초과 발생 가능성이 있다.
    • 이동 경로를 모두 찾는 게 아니라 이동 가능한 칸 수의 최댓값을 구하는 것이므로 DFS는 적절하지 않는다.
• 시도2(맞음)
  • 접근 방법
    • 이동할 수 있는 규칙이 제한되어 있다. (체스판 위 나이트 이동과 유사)
    • 이동 규칙 중 2칸 위로 1칸 옆으로 이동만 가능하므로 가능한 이동 방식이 총 4가지이다.
    • 문제에서 주어진 조건을 기반으로 그리디하게 분기 처리하였다.
  • 풀이 핵심
    • 세로 길이가 1인 경우: 이동 불가 → 1
    • 세로 길이가 2인 경우: 이동 가능한 칸이 제한됨 → min(4, (가로 - 1) / 2 + 1)
    • 세로가 3 이상인 경우
      • 가로가 7 미만일 경우 → min(4, 가로)
      • 가로가 7 이상일 경우 → 가로로 - 2
  • 소스 코드

  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception {
          // 입력
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String[] tmp = br.readLine().split(" ");
          int n = Integer.parseInt(tmp[0]);  // 세로
          int m = Integer.parseInt(tmp[1]);  // 가로
  
          int result = 0;
  
          if (n == 1) {
              // 이동 불가, 시작칸만 방문
              result = 1;
          } else if (n == 2) {
              // 위아래 이동이 안되니, (1,2), (-1,2)만 사용 가능 => 4번까지만 가능
              result = Math.min(4, (m + 1) / 2);
          } else if (n >= 3 && m < 7) {
              // 위아래는 충분하지만 오른쪽 이동이 부족해서 4가지 이동을 다 못 씀
              result = Math.min(4, m);
          } else {
              // 4가지 이동 다 사용 가능
              result = m - 2;
          }
  
          // 출력
          System.out.println(result);
      }
  }

3. 오늘의 회고

• 문제 상황과 시도

문제를 처음 보고 DFS로 모든 경로를 탐색해야 하는 건가 싶었다. 방문한 칸의 수를 최대화하려면 모든 경우를 봐야 한다고 생각했기 때문이다.

• 해결 과정

하지만 힌트를 보니 이 문제는 탐욕법으로 푸는 것이 적절하다는 것을 알게 되었고 그 순간 내가 접근했던 방식이 잘못되었음을 깨달았다. 이후 조건을 분기 처리하는 방식으로 접근했더니 훨씬 간결하고 효율적으로 문제를 해결할 수 있었다.

• 배운 점

이 문제는 단순히 이동 규칙을 구현하는 것이 아니라, 제한된 조건 안에서 최적의 해를 찾는 것이 핵심이었다. 앞으로는 문제의 조건을 잘 분석하고 거기에 맞는 알고리즘이 무엇인지 먼저 판단하는 연습을 더 많이 해야겠다고 느꼈다.