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

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

문제 https://www.acmicpc.net/problem/10472 10472번: 십자뒤집기 당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색 www.acmicpc.net 풀이 과정 데이터는 3x3으로 총 9개의 수가 주어지므로, int하나로 비트마스킹을 사용했다. 특정 상태까지의 최단 시간을 구하는 문제이므로 BFS를 사용했고 검은색은 1, 흰색은 0으로 비트마스킹해서 전체 값이 0이면 모두 흰색이므로 종료하도록 했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

1. 문제 https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 2. 풀이과정 [방법 1] DFS + 새로운 배열 선언 방식 새로운 배열을 만들어서 DFS를 구현했다. 메모리는 많이 사용하지만, 메서드가 종료될 때 배열을 원상태로 되돌리지 않아도 돼서 빠르다. 마지막에 요소가 2개 남았을 때, 최대값을 업데이트해주고 종료한다. import java.io.BufferedReader; import java.io.InputStreamReader; i..

1. 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 2. 풀이과정 문제대로 구현하면 되는 문제이고, 톱니바퀴를 회전할 때는 배열의 모든 값을 오른쪽 혹은 왼쪽으로 움직이지 않고 시작 포인트만 변경해서 얼만큼 회전했는지 표현했다. 그리고 가장 왼쪽, 오른쪽의 값은 나머지 연산을 통해 시작에서 각각 2번째, 6번째에 떨어진 값을 반환하도록 했다. import java.io.BufferedReader; import java.io.Inpu..

1. 문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 풀이 과정 처음에는 간단하게 (해당 데이터에서 최대 길이) = (해당 데이터보다 작고 앞에 있는 것 중 가장 큰 값) + 1을 해서 이중for문으로 구현했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public stat..

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