Algorithm
[JAVA] 백준 16567 : 바이너리 왕국
문제 16567번: 바이너리 왕국 첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다. 그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0 www.acmicpc.net 해결 방법 간단한 문제인데 조건을 빼먹어서 오래 걸렸습니다. 처음에 바닥의 상태가 주어질 때 연속으로 더러운지 아닌지 확인하면서 카운트를 증가시켜줘야합니다. 다음에 M개의 명령이 주어질 때 0의 경우일 때는 카운트를 출력하고 1의 경우일 때는 총 4가지를 생각해야합니다. 1. index가 0일 때 자신의 다음 칸이 깨끗하다면 카운트를 1증가 2. index가 마지막일 때 자신의 이전 칸이 깨끗하다면 카운트를 1증가 3. 그 외..
[JAVA] 백준 1637 : 날카로운 눈
문제 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 해결방법 개인적으로 이해하는데에 많은 시간을 소모해서 다음에 이와 같은 문제를 봤을 때 이해하는 속도를 높히고자 글을 작성해둔다. 이 문제는 정수더미에 수 많은 숫자들이 들어있고, 그 중에서 하나의 숫자만 홀수개 존재하는데 그래서 정수더미에 있는 수 중 홀수개 존재하는 숫자가 무엇인지 또 몇 개 들어있는지를 출력하는 문제이다. 예제 1의 입력을 보면 1 10 1 과 같이 3개의 숫자가 주어지는데 의미는 ..
[JAVA] 백준 13913 : 숨바꼭질 4
문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결 방법 오랜만에 알고리즘 해설을 준비했는데, 그리 어렵지 않은 문제이다. 어려운 문제는 어떻게 풀어야 할지 아직 감이 잘 안 잡혀서, 문제를 풀더라도 설명을 할 정도로 이해를 하지 못해 가져오지 못했다. 이 문제는 수빈이가 동생을 찾는 숨바꼭질 문제인데, 수빈이는 현재 위치에서 +1, -1 또는 x2 만큼 움직일 수 있고 움직일 때마다 1초씩 소모된다. 즉, 모든 경우의 수를 전부 확인하며 목표지점에 도달하는 시간을 체크..
[JAVA] 백준 16946 : 벽 부수고 이동하기 4
문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해결 방법 어떤 방식으로 해결해야 되는지 몰라 다른 블로그를 참고했다. 참고한 블로그는 이 곳이다 -> https://devowen.com/253 Flood Fill, 즉 플러드 필 알고리즘을 사용해야 한다고 하는데 위 블로그에 자세히 설명되어있다. 문제를 보게되면, 벽과 이동할 수 있는 공간이 존재한다. 벽에 해당하는 부분은 부순다음 해당 칸에서 이동할 수 있는 칸의 개수를 계산해서 벽이었던 1의 해당하는 부분은 해당 칸에서 이동할 수..
[JAVA] 백준 2151 : 거울 설치
문제 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 해결 방법 빛은 일직선으로 나아가고, 45도 각도의 거울을 사용해서 이동방향을 바꿔 목적지에 도착하도록 하는 문제이다. 그래서 현재 방향이 어디인지 저장할 dir을 사용하고, cnt를 사용해서 거울을 몇 번 사용했는지 체크하게끔 class를 구성했다.또 우선순위 큐를 사용해서 가장 거울을 적게 사용한 결괏값이 제일 먼저 목적지에 도착하도록 하였다. 시작점과 도착점이 문제와 같이 2개만 주어지는 문제는 처음 입력을 받을 때 해당 지점을 체크해두고..