2253 : 점프 처음에는 갈 수 있는 가지수인줄 알았는데 최소 움직임 횟수였다. 명심할 것 문제 잘 꼼꼼히 읽기 경계값 체크하기기존 코드에서는 2번째 칸을 무조건 이동가능하게 해뒀는데 2번째 칸 역시 작아서 밟지 못할 수 있다. 이 부분에서 문제가 생겨서 계속 오류가 났다. 예제와 같이 6, 11, 16번 칸을 못 밟는 경우 아래와 같다. 1번째 칸에서 한칸만 이동 가능하다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 0 1 2 3 4 5 6 7 2번째 칸에서는 1의 속도로 점프했으므로 다시 1의 속도로 점프하거나, 가속해서 2의 속도로 점프할 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 0 1..
Problem Solving/백준
톱니바퀴를 회전시킬 때는 방향과 회전시킬 톱니바퀴를 선택한다. 톱니바퀴와 맞닿은 다른 톱니바퀴의 극이 서로 다르다면 → 맞닿은 톱니바퀴는 해당 톱니바퀴의 반대방향으로 회전 모든 회전이 끝나면 12시방향이 S극이면 + 2^(N - 1) 점 3번 톱니바퀴는 맞닿아있는 4번 톱니바퀴와 극이 다르다. 1회전 시 3번 톱니바퀴는 반시계, 4번 톱니바퀴가 시계방향으로 움직인다. 이제 1번 바퀴를 시계 방향으로 움직인다. 2번 바퀴와 극이 다르므로 2번은 반시계방향으로 움직인다. 1,2,3번 바퀴가 12시방향에 S극이다. 따라서, 1 + 2 + 4 = 7점 K가 100으로 매우 작음 오른쪽 바퀴 회전 여부 → 현재 바퀴[2]와 다음 바퀴[6]이 서로 다른지 확인 왼쪽 바퀴 회전 여부 → 현재 바퀴[6]과 다음 바퀴[..
13913번: 숨바꼭질 4 처음에는 Move 클래스 안에 StringBuilder나 StringBuffer를 넣어서 이전의 경로를 복사해서 최종 경로를 찍도록 했는데 시간 초과가 났다. 아무래도 복사 비용과 새 인스턴스 생성하는 비용이 커서 그런 것 같다. 그래서 예전에 봤던 방법을 사용했는데 prev 배열에 직전 경로를 저장하는 방법이다. prev[a] = b 는 a로 가기위해서는 b를 거친다는 의미이다. 이후 아래와 같이 마지막 K부터 시작점 N까지의 경로를 추적해서 출력하면 된다. int index = K; while(index != N){ index = prev[index]; } 방문 처리 위치에 따라 직전 경로가 갱신이 될 수 있기 때문에 방문 처리 위치도 중요하다. static void BFS..
1202번: 보석 도둑 아이디어 생각해내는게 너무 어려웠다. 처음에는 보석 이 들어가길래 습관적 DP로 생각했는데, 각 가방의 크기가 너무 커서 배열로 담을 순 없다는 것을 깨달았다. 그래서 ‘가방의 사이즈를 배열의 값으로 담아 K개 저장한뒤 오름차순으로 정렬해야겠다’까지는 쉽게 생각이 났다. 그 뒤로 한 시간 이상 고민했고, 풀이방법만 봐야겠다 싶어 확인해봤는데 아이디어는 간단했다. 우선순위 큐를 두개 준비한다. 하나는 무게를 오름차순으로 정렬하고 하나는 가치를 기준으로 정렬할 것이다. 이를 각각 pqByWeight와 pqByValue라고 하겠다. 입력받은 모든 보석들을 pqByWeight에 넣는다. 가방을 입력받고 가방의 최대무게를 오름차순으로 정렬한다. 각 가방의 최대 무게마다 해당 무게보다 낮은 ..
