네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 2. 풀이 과정 처음에는 오는 방향에 따라 들어온 방향과 같으면 거울 수를 추가하지 않고, 들어온 방향과 다르면 거울 수를 추가해서 처리했다. PriorityQueue를 사용해서 사용한 거울 수가 작은 경로부터 처리해서 도착지가 나오면 종료했다. 코드는 아래에 [더보기]를 클릭하면 볼 수 있다. 더보기 import java.io.BufferedReader; import java..

1. 문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 2. 풀이 과정 [방법1] LinkedList + Iterator 처음에는 LinkedList를 사용해서 풀었다. LinkedList를 선택한 이유는 리스트 중간에 값을 삽입하고 삭제하는 과정이 빠르기 때문이다. 하지만 시간초과가 났다. 기존 코드에서는 커서가 있는 값을 index를 써서 해당 위치에 있는 값을 찾았기 때문에, LinkedList는 맨 처음 요소부터 index번째에 있는 ..

1. 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 과정 [방법1] PriorityQueue를 이용한 BFS 도착 지점이 출발 지점보다 작은 경우, 빼기만 해서 가는 것이 가장 빠르므로 N-K를 출력한다. 아닌 경우는 PriorityQueue를 써서, 현재 최소 경로인 값에 +1, -1, *2 를 해본다. 더보기 import java.io.BufferedReader; import java.io..

1. 문제 https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 2. 풀이과정 자라는 정도가 아래에서 위로 & 왼쪽에서 오른쪽으로 갈수록 증가한다. 따라서 가장 왼쪽 열과 가장 위쪽 행을 제외한 다른 칸들은 윗칸과 동일한 값을 가질 수 밖에 없다. 날짜수만큼 반복문을 돌면서, +1이 시작하는 위치와 +2가 시작하는 위치를 계산해서 해당 위치에 +1을 해준다. 반복문이 끝나면 증가량을 기록한 배열의 0번째 부터 끝까지 돌면서 ..

1. 문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B로 BFS를 사용해서 풀었었고, 나중에 다른 코드를 참고한 후에 B -> A로 갈 수 있는지 확인해가는 방식으로 풀게 됐다. 먼저 마지막이 1로 끝나는 수는 홀수 중에 하나이므로 연산을 홀수일 때, 짝수일 때로 나눠볼 수 있다. 짝수면 /2를 하고, 홀수 중에 1로 끝나면 /10을 한다. 둘 다 해당하지 않는 수는 만들 수 없는 수로 끝내면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import j..

1. 문제 https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 2. 풀이 과정 배열의 크기가 1000x1000이므로, DFS와 같은 완탐으로는 시간 초과가 날 것 같아서 DP로 시도했다. 아직 DP문제는 푸는 데 시간이 좀 걸린다.. 딸기 우유, 초코 우유, 바나나 우유 3가지 경우를 나눠서 생각하기 위해서 DP를 3차원 배열로 구현했다. 중간에 안 먹고 건너 뛸 수도 있어서 마지막에 어떤 종류를 먹었는지를 고려해주기 위해서다. 전체 배열을 2차원 배..

1. 문제 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 2. 풀이 과정 흔히 union & find를 구현할 때, find에서 사이클 여부를 판단한다. 이 문제는 find의 로직과 유사하게 구현할 수 있다. 사이클이 되는 모든 값을 결과로 출력하면 되는 문젠데, 처음부터 그래프 유형인걸 파악못해서 시간이 걸렸다. 1. for문으로 첫 번째 줄의 값을 처음부터 끝까지 탐색한다. 2. 각 값마다 cycle이 되는지 확인하고, cyc..

1. 문제 https://www.acmicpc.net/problem/2374 2374번: 같은 수로 만들기 n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한 www.acmicpc.net 2. 풀이과정 문제 유형에 stack이 써있는 걸 보고 풀었다. 안 보고 풀었으면 생각해내기 어려웠을 것 같았다. 입력을 처음부터 끝까지 받으면서, 구간마다 최소값을 찾아서 큰 값에서 뺀 값을 결과에 더해주었다. 마지막에 최대값에서 stack의 top에 있는 값을 빼주는 이유는 값이 감소하면서 끝날 경우 앞서 나온 최댓..

1. 문제 https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 2. 풀이 과정 방법 1. DFS 열어야 하는 문이 왼쪽 열린 문과 오른쪽 열린 문 사이에 있다면, 깊이 우선 탐색으로 둘 다 탐색해본다. 열어야 하는 문이 두 개의 열린 문보다 왼쪽에 있다면, 왼쪽 열린 문을 당겨와서 사용한다. 열어야 하는 문이 두 개의 열린 문보다 오른쪽에 있다면, 오른쪽 열린 문을 당겨와서 사용한다. 이때, 현재까지 구한 결과 값보다 중간 값이 이미 크다면 더..

1. 문제 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 2. 풀이 과정 최단 경로를 구하는데, 지나온 길을 다시 탐색할 수 있기 때문에 플로이드 워샬 알고리즘으로 각 노드마다 갈 수 있는 최단 거리를 구하고 DFS 탐색을 했다. 이때, DFS 탐색의 결과는 어떤 노드를 먼저 방문하냐 즉 방문하는 노드 순서에 따라 달라지므로 순열 탐색으로 볼 수 있다. import java.io.BufferedReader; import java.io.I..