boj)5904 - Moo 게임
2020. 11. 15. 13:00ㆍPS/boj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import java.util.Scanner;
public class boj_5904 {
static Scanner sc = new Scanner(System.in);
static int[] dp = new int[30];
public static void main(String[] args) {
int N = sc.nextInt();
dp[0] = 3;
for (int i = 1; i < dp.length; i++) {
dp[i] = (dp[i-1]*2) + (i + 3);
}
System.out.println(func(N));
}
static char func(int n) {
if (n == 1) return 'm';
if (n == 2 || n == 3) return 'o';
int i = 0;
while (dp[i] < n) i++;
if (dp[i] == n) return 'o'; // 끝
if (n - dp[i - 1] == 1) return 'm'; // 다음 칸
if (n - dp[i - 1] <= i + 3) return 'o'; // moo.... 에서 o 해당하는 칸
return func((n - dp[i - 1] - (i + 3)));
}
}
|
cs |
- 재귀, dp
- 길이 구하는 점화식이랑 규칙은 눈에 보이는데 함수 식을 어떻게 세울지 생각이 안났다.
- 어려움
- 길이는 주어진 식대로 S(k) = S(k-1) * 2 + (3 + k) 로 구할 수 있고 거의 2배씩 늘어나고 2^30 >= 10억
이니까 dp에 길이를 30까지만 저장해준다,
- base condition 으로 'moo' 에 맞게 설정한다.
- int i 값을 이용해서 지금 n이 S의 몇번째 index인지 찾아준다.
- S(k-1) | m o o .... | S(k-1) 에서 m o o .... 에 해당하는 부분을 따로 처리해주고 해당하지 않으면
n - dp[i-1] - (i+3) 을 다시 호출한다.
'PS > boj' 카테고리의 다른 글
boj)15650 - N과 M (2) (0) | 2020.11.16 |
---|---|
boj)15649 - N과 M (1) (0) | 2020.11.16 |
boj)2447 - 별 찍기 - 10 (0) | 2020.11.14 |
boj)16505 - 별 (0) | 2020.11.14 |
boj)1992 - 쿼드트리 (0) | 2020.11.13 |