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

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

문제 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 풀이 과정 코드를 작성하기 전에는 각 문자를 인덱스로 써서 문자별 개수를 cnt하고 이를 비교해야겠다까지 설계하고 시작했다. 하지만, 첫 번째 문자열 길이가 더 큰지, 주어지는 문자열 길이가 더 큰지 등 조건까지 같이 떠올리는 연습이 필요한 것 같다. 아래는 문자열 길이 차이가 2이상이면 비교 연산없이 다음 문자열로 넘어간다. 2미만이면 같은 문자의 개수가 몇 개인지 count하여 주어진 ..

문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 과정 가능한 경로 중 가장 짧은 경로를 찾아야 하므로, BFS로 풀었다. 여기서 해당 경로 과정을 기록할 때는 Queue에 문자열을 넣어도되지만, 문자열을 합치는 비용이 크다. 따라서, 아래와 같이 해당 숫자의 index에 D, S, L, R중 어떤 명령어로 왔는지를 char형으로 저장해놓는다. 결과를 출력할 때는 parent배열을 따라 역으로 올라가면서, 경로를 합쳐준다...