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

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..

1. 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 2. 풀이 과정 특정 상태까지의 최소 이동 시간을 구하기 때문에, BFS로 탐색하였다. 여기서 고민했던 부분은 방문 체크였다. 이미 이전에 고려했던 2차원 배열의 상태는 다시 볼 필요가 없기 때문에, 이 2차원 배열을 int형 숫자하나인 123456780 식으로 변환해서 방문체크를 하고 너비우선탐색을 진행했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; p..

1. 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 풀이 과정 최단 경로를 구하는 데, 경로의 cost가 음수가 될 수 있기 때문에 Bellman-Ford 알고리즘을 사용했다. 평소에 잘 풀어보지 않았던 유형이라서 시간이 걸렸다.. 벨만-포드 알고리즘은 다익스트라와 유사한데, 다익스트라는 현재 연결된 노드에서 갈 수 있는 경로를 살펴보며 값을 업데이트하는 반면 벨만-포드 ..

1. 문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 풀이 과정 처음엔 DFS로 모든 경로를 처음부터 끝까지 탐색하도록 했고, 시간 초과가 났다. 아래 그림과 유사하게, 출발점에서 도달할 수 있는 좌표에 +1을 해나가며 값을 업데이트하고 결과는 (N, N)의 값을 출력해주면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..