백준 이제는 더 이상 물러날 곳이 없다 (99클럽 코딩테스트 29일차 TIL)

목표

5월9일 스터디가 끝나기 때문에 그전까지 문제를 열심히 푸는게 목표이다.

문제

내가 생각했을때 문제에서 원하는부분

자신의 차례에 아래 두 가지 행동 중 하나를 반드시 수행해야 한다. 전장을 벗어나도록 이동할 수 없으며, 행동을 마친 뒤에는 상대방의 차례가 된다.
좌우로 인접한 칸으로 이동한다.
좌우로 인접한 칸에 상대방이 있다면, 상대방을 공격한다.
상대방을 공격하는 경우 승리한다.

내가 이 문제를 보고 생각해본 부분

문제에서 건덕이와 건구스가 가로로 놓인 저장에서 서로 반대편 끝(왼쪽, 오른쪽)에서 출발한다고 했다.
그리고 번갈아가면서 한 칸씩 옆으로 이동할 수 있다고 했다.
전장의 가운데에서 만나면 먼저 이동하는 사람이 공격할 수 있다고 했다.
여기서 전장의 칸의 개수 N에 따라 가운데에서 먼저 공격할 수 있는 사람이 바뀐다는 것을 알게됐다.
N이 짝수일때는 항상 건덕이가 먼저 도착하고 홀수일 때는 항상 건구스가 먼저 도착한다.
즉 N을 2로 나눈 나머지로 짝수 홀수를 판별할 수 있다.
그래서 나머지가 0이면 건덕이 승리 0이 아니면 건구스 승리로 결정할 수 있다.

코드로 구현

package baekjoon.baekjoon_18;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 백준 30455번 문제
public class Main632 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        if(N % 2 == 0) {
            System.out.println("Duck");
        } else {
            System.out.println("Goose");
        }
        br.close();
    }
}

시간복잡도 O(1)

장점
입력값의 크기와 상관없이 항상 일정한 시간이 소요된다.
시간 복잡도 관점에서 가장 효율적인 알고리즘이다.

단점
입력값에 대한 추가적인 연산이 필요한 경우 시간복잡도가 증가할 수 있다.
문제 상황에 따라 O(1)으로 알고리즘을 설계하기 어려울 수 있다.

마무리

오늘 풀어본 문제는 정말 간단하게 해겨할 수 있는 문제였다. 이런 문제를 볼때 처음에는 어렵게 느껴졌는데 막상 조금만 생각하고 코드를 작성하면 근방 해결할 수 있는 문제였던것같다.