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

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

문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이과정 각 번호별로 먹은 횟수를 1차원 배열에 기록했다. 여기서 인덱스는 음식의 번호를 의미한다. 이 문제에서는 K개라는 window크기가 정해져있으므로 window를 한칸씩 오른쪽으로 움직여가며 값을 계산했다. window가 옮겨질 때는 window맨 첫번째 수를 빼주고 다음 수를 하나 더해주는 방식으로 진행한다. import java.io.Buff..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 과정 대각선 위, 중간, 대각선 아래 순서대로 탐색해서 최대로 설치할 수 있는 개수를 구할 수 있다. 이때, 한 노드에서 갈 수 있는 경로를 모두 탐색했을 때 못가는 경로로 판단날 경우 다시 가볼 필요가 없기 때문에 방문한 모든 노드는 'x'처리한다. 또한, 갈 수 있는 경로는 이제 사용한 경로로 취급되어 다음 경로는 여기를 지나칠 수 없으므로 'x'처리하기 때문에 결과적으로 방문한 모든 노드를 'x'..

문제 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 풀이 과정 각 수마다 변경될 때 반전이 필요한 횟수를 arr배열에 저장했고, 이 코드는 미리 짜서 돌린후 대입해서 실제 코드에서는 넣지 않았다. 고정적인 값이라서 굳이 계속 돌릴 필요가 없다고 판단했다. DFS를 통해서, 모든 경우의 수를 탐색한다. 여기서 (자리수, 10^(자리수), 현재까지 수, 반전시킨 횟수)를 인자로 넣어서 반전 시킨 횟수도 최대 횟수를 넘지않고, 현재 수가 N층을 넘지 않으면 통과시킨다. 이때 K자리까지 다 탐색했으면 결과+1을 하고 마지막엔 -1을 해..

문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 과정 가장 큰 값만 넣기 위해 가장 아래의 row값들을 PriorityQueue에 넣었다. N-1개를 꺼내면서 꺼낸 값의 앞 row에 있는 값을 또 넣어주며, N번째로 큰 수를 찾았다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.Str..

문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 과정 처음에는 Ai 범위를 양수로 보고 2중 for문과 집합을 사용해서 풀었다. 하지만, Ai는 음의 정수, 0, 양의 정수를 모두 포함하기 때문에, 0 + 자기자신으로 true를 반환해서 틀렸다. 범위를 다시 파악하고 나서는 배열을 정렬한 후, 가장 왼쪽 값과 가장 오른쪽 값을 더해가면서 값이 현재값보다 작으면 더 큰 수를 더해줘야 하므로 left+1을 해주고, 크면 right-1을 하여 가능할 것 같은 값만 빠..

문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 풀이 과정 큰 건물에는 가려질 수 있지만, 작은 건물에는 가려질 수 없다. 따라서 stack을 이용해서 자신보다 큰 값은 pop으로 꺼내면서 건물의 개수를 카운트했다. 그리고 Stack에 값을 넣을 때는 stack의 top에 이미 같은 값이 있다면, 같은 건물일 가능성이 있으므로 넘어갔다. 마지막으로 stack에 오름차순으로 모두 다른 값..

문제 https://www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 풀이 과정 주어진 문자열을 숫자로 나타내면 다음과 같이 볼 수 있다. abcde fghij klmno pqrst uvwxy z HELLO = 8 5 12 12 15 DRINK = 4 18 9 14 11 SHUTTLE = 19 8 21 20 20 12 5 여기서 다음 수를 구할 때는, 뒤에서 부터 봤을 때 오름차순으로 올라가다가 꺾이는 지점의 수(top) 이전 값과 그 이후의 숫자 ..

문제 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 과정 첫 번째 스위치의 상태가 정해지면, 나머지 전구를 꺼야하는지가 결정된다. 따라서 첫 번째 스위치를 눌렀을 때와 안 눌렀을 때 2가지 경우에 대해 최솟값을 반환한다. 각 스위치를 누를지 말지 결정하는 기준은 자기 앞의 값이 목표 상태와 같은지 보고 결정하면 된다. import java.io.BufferedReader; import java.io.Input..

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 풀이 과정 특정 노드로 부터 모든 노드의 최단 거리를 저장하기 때문에, BFS 탐색을 했다. 결과 배열에 각 칸을 처음 방문했을 때, (이전 칸의 값 + 1)로 바로 값을 넣는다. 값이 이미 있다면 전에 더 짧은 경로로 왔다는 의미이므로 넘어간다. import java.io.BufferedReader; import java.io.InputStrea..