병든 나이트 : https://www.acmicpc.net/problem/1783
제약 조건:
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다.
병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.
이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
조건을 쓴 사람의 설명이 부족한건지 이해하지 못한 내가 멍청한 건지..
이동 방법에 제약이 없다는 말의 의미를 해석할 때, 머리가 터질것 같았다.
처음엔 이동방법에 제약이 없다는 말을 4방향 +1칸씩 이동가능하며 이를 횟수로 4번 가능하다 라고 해석해서 실패했다.
아무리 예시에 대입해도 답이 나오지 않음.
참조 : https://data-make.tistory.com/653
위의 사이트를 참조하고 나서 겨우 의미가 이해가 되었고 문제가 해결됐다.
말의 움직임은 문제에 주어진 대로만 가능하며 이동방법에 제약이 없다는 것은 제시된 움직 중 각각의 동작을 4번까지 할 수 있다는 것이다.
이 조건을 이해하면 그림만 그려보면 답이 나온다.
#N=1
말이 행동할 수 있는 경우 없음.
#N=2
2칸 증가할 때마다 행동이 하나씩 늘어남.
1,1
2,1
3,2
4,2
5,3,
6,3
7,4
8,4
9,4
4회 이동까지만 허용되므로 m이 홀수인 경우 몫이 반올림 되지 않으므로 +1을 해준 뒤 몫을 취한다.
answer = min ( 4, (m+1)/2) 가 된다.
#N=3
M 1한칸당 1개씩 늘어난다.
M < 7 인 경우, N=2와 같은 이유로 4개가 최대가 되며 M=7을 기점으로 M 한칸당 1개씩 증가한다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int N, M;
static boolean DBG = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int answer = 1;
if( N == 1)
answer = 1;
else if (N == 2)
answer = Math.min(4, (M+1)/2);
else if (M < 7 ) {
answer = Math.min(4, M);
} else {
answer = 5 + (M-7);
}
System.out.println(answer);
}
}
