-
[백준 - 17370번] 육각형 우리속의 개미 - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 8. 6. 15:28
이번에는 BOJ의 17370번 "육각형 우리속의 개미" 문제를 풀어보도록 하자
여기에서 눈여겨 봐야 할 점은
- 처음에 이동은 편의상 반드시 북쪽(위쪽)으로 이동한다
- 개미가 변이 세갈레인 점에 도착하면, 자신이 이동해온 변을 제외한 나머지 두 변 중 하나를 골라 그 방향으로 회전
- 입력으로 주어지는 정수 N의 크기가 (1 <= N <= 22)
이렇게 3가지이다. 이것에 유의해서 이동하는 경로에 가중치를 넣어서 각점을 유니크한 값으로 만들어 준다. 가중치는 각 북쪽(위쪽) 경로를 기준으로 시계 방향으로 [23, 1, 1, -23, -1, -1] 로 해주었고, 이를 통해 답을 구하기 위해서 boolean 배열을 chk로 지정해주고, 총 크기를 2001(임의의 값, 반드시 23 * 22 * 2 보다는 크게 해줬다.)로 해준다. 맨처음 위치를 1000으로 하면, chk[1000]을 true로 해주고 위치 1000부터 시작해서 맨처음 북쪽(위쪽)으로 이동 하기 때문에, 위치가 1023 점을 지나게 되니, 먼저 현재 방향회전을 한 횟수 cnt 가 0인지 아닌지 판단해주고, 그다음에 chk[1023]이 true인지 false 인지 판단 해주고, 다음 방향회전을 진행하게 해주면 된다.
성공한 코드는 아래와 같다.
import java.io.*; import java.util.*; public class sample { static boolean[] chk = new boolean[2001]; static int[] weight = { 23, 1, 1, -23, -1, -1 }; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); chk[1000] = true; bw.write(calc(N, 1000 + weight[0], 0) + "\n"); bw.flush(); br.close(); bw.close(); } static int calc(int cnt, int cur, int w) { if (cnt == 0) { if (chk[cur]) return 1; else return 0; } if (chk[cur]) return 0; chk[cur] = true; int temp = calc(cnt - 1, cur + weight[(w + 5) % 6], (w + 5) % 6) + calc(cnt - 1, cur + weight[(w + 1) % 6], (w + 1) % 6); chk[cur] = false; return temp; } }
문제 : https://www.acmicpc.net/problem/17370
'Algorithm > BOJ(Baekjoon Online Judge)' 카테고리의 다른 글
[백준 - 2003번] 수들의 합 2 -Java //Wello Horld// (0) 2019.08.06 [백준 - 17355번] Messi An-Gimossi - Java //Wello Horld// (0) 2019.08.06 [백준 - 13277번] 큰 수 곱셈 - Java //Wello Horld// (0) 2019.08.06 [백준 - 17363번] 우유가 넘어지면? - Java //Wello Horld// (0) 2019.08.06 [백준 - 17362번] 수학은 체육과목 입니다 2 - Java //Wello Horld// (0) 2019.08.06