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

문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 과정 왼쪽, 왼쪽의 대각선, 위쪽에서 제일 작은 정사각형 크기 + 1이 현재 노드에서의 정사각형의 크기로 한다. 자신보다 아래에 위치한 1들은 나중에 고려하므로 생각하지 않는다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args)..

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 과정 dp[i] = (dp[i-1][x] + dp[i-1][1] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][1]) = dp[i-1]*2 + dp[i-1][x] = dp[i-1]*2 + dp[i-2] import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception..

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 과정 처음엔, 3방향 다 Math.max로 고려해줬었다. 하지만, 최단 거리가 아니기 때문에, 대각선에서 오는 것보다 위 혹은 왼쪽을 거쳐 오는 것이 총 사탕 개수가 같거나 큰 경로이므로 대각선은 고려하지 않는 것이 효율적이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 과정 처음에, 어차피 왼쪽에서 오른쪽, 위에서 아래로만 움직일 수 있기 때문에 2중 반복문으로 풀 수 있을 것 같았다. 하지만, 방향까지 고려해야 돼서 생각하다가 DFS로 풀었다. 다 풀고나서, 고민하다가 방향마다 따라 결과를 저장해가면 2중 반복문으로 풀 수 있을 것 같아서 다시 풀었다. 결과적으로 속도가 2배 향상되었다. 이전 코드 : DFS import j..

1. 문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 2. 풀이 과정 최대한 원래 줄을 안 건드리고 새로 줄 세우는 방법이 가장 빠르다. 따라서 원래 줄 중에서 가장 긴 부분 수열(LIS, Longest Increasing Subsequence)을 찾으면 된다. 결괏값은 전체 아이들의 수인 N - 가장 긴 부분 수열의 길이가 된다. import java.io.BufferedReader; import java.io.InputStreamReader;..

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

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

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

1. 문제 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 2. 풀이과정 풀이방법은 2가지가 있다. 위상 정렬 문제를 많이 접해보지 않아서 헤맸던 문제다. 1. 위상정렬 선행 요소를 입력 받을 때, 선행요소에 '나'를 추가하는 방식으로 한다. 즉, 모든 노드들의 후행요소로 저장해주는 것이다. 0번째 작업부터 차례대로 돌면서, 자신의 뒤에 실행할 곳에 수행 시간을 더해준다.이때, 선행 요소가 여러 개 있는 작업은 수행 시간이 가장 긴 선..