개발하는 고라니

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net [Deque, 문자열] 문제는 상당히 직관적이고 길지 않아서 이해하는데 어려움은 없지만, 생각한 것을 구현을 할 수 있느냐에 관한 문제와 시간, 메모리의 효율 그리고 자료구조 덱(Deque)을 알고 있는가에 대한 문제가 있다. 아, 그리고 원소의 값으로 주어지는 것이 한 자릿수가 아님에 절대로 유의하자. 이 점을 간과하여 덱을 쓰지않고 문자열 객체로만 할 수 있을 줄 알았으나, 원소의 값은 1 이상 100 이하이다. 덱이란 간단히 말해, 큐(Queue)가 선입선출(First-in First-out, FIFO)이라면, ..

5884번: 감시 카메라 총 소가 6마리 있고, 소의 위치는 (1,7), (0,0), (1,2), (2,0), (1,4), (3,4) 이다. 감시 카메라를 y=0, x=1, y=4 로 설치하면 모든 소를 감시할 수 있다. www.acmicpc.net [Map 이용] Java의 Map 컬렉션을 사용했다. 문제의 접근법은 간단하며 다음과 같다. 2차원 배열에 소들의 (x, y) 좌표를 저장한다. x좌표 Map과 y좌표 Map을 준비한다. x좌표 Map에 Key로 좌표를, Value로 빈도수를 저장한다. y좌표 Map에도 마찬가지 감시 카메라는 총 3대이므로 3번의 반복문을 수행한다 xMap에서의 가장 많이 위치한 x좌표의 정보를 꺼낸다. yMap에서의 가장 많이 위치한 y좌표의 정부를 꺼낸다. (1), (2..

16441번: 아기돼지와 늑대 첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열 www.acmicpc.net [BFS] 빙판('+')만 주의하면 될 문제인줄 알고 섯불리 제출했다가 오답처리를 당했다. 그 이유는 조금 뒤에서 설명하고 우선 문제의 접근법은, 문제에서 주어진 입력을 받으며 늑대의 위치를 기억한다. 그리고 BFS 함수의 인자로 늑대들의 위치를 준다 늑대들의 위치에서 각자 BFS를 수행하는데, 빙판('+')을 만나면 산('#')이나 초원('.')을 만날 때 까지 쭉 미끄러진다. 이 부분을 구현하는 메서드는 다음과 같다. /* di..

1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 이 문제를 보고 실제로 불을 껏다 켰다 할 생각을 하니 막막했었는데.. 그런 생각을 한 것 자체가 너무 1차원적이어서 다른 분의 풀이를 참고하였다. 역시나 스위치를 올렸다 내렸다 하는 일은 존재하지 않았고 패턴을 찾는 것이 관건이었다. 먼저 모든 행을 돌며 각 행에 포함된 0(off)의 개수를 센다. 당연히 0의 개수는 K보다 작거나 같아야 한다. 그 행의 불을 켜려면 0의 개수가 K개 보다 많으면 안되니 말이다. 그리고 이것이 중요한데 K가 짝수라면 0..

9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net [동적 프로그래밍] 동적 프로그래밍으로 풀어도 되고, 홀/짝으로 풀어도 된다. 상근이가 [1, 3, 5, 7, 9, ...] 즉 홀수일때 반드시 이기고, 창영이는 나머지 짝수일 때 반드시 이긴다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(..

16768번: Mooyo Mooyo In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000 www.acmicpc.net [DFS] 뿌요뿌요(?)와 비슷한 방식의 게임이라고 하며, 0은 빈 칸이고, 1~9로 이루어진 각각 다른 색의 세포가 10 x N 격자에 있는데 최소 K개의 같은 색인 인접(상하좌우)한 세..

17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net [BFS + 비트마스크] N x M 격자 맵에서 'X'로 표시된 모든 물건을 챙기고 탈출구 'E'로 최소한의 움직임으로 나가는 방법을 찾는 문제. 격자의 크기 제한이 최대 50x50이고 물건의 개수가 최대 5개라서 비트마스킹을 안써도 메모리적인 부분에서 큰 손실은 없을 것 같으나, 물건이 모두 'X'로 동일하여 현재 내가 특정 정점에 방문했을 때, 어떤 물건을 갖고 있는 지를 체크하는 것이 비트마스킹만큼 좋은 것이 없기에 비트마스킹을 사용했다. 먼저 입력을..

12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net [BFS] 브루트포스로 푼다면 문제 자체의 난이도는 비교적 간단한 편이나, 브루트 포스로 푼다면 메모리 소모가 엄청나므로 최대한 효율적인 방법으로 중복 점을 제거하여야 한다. 여러 방법이 있을 수 있다. 나는 정렬을 사용했다. 브루트 포스를 사용한다면 방문을 체크하는 정점 배열을 [1501][1501][1501] 만큼의 배열을 사용해야하지만, 정렬을 사용하면 [501][1001][1501] 정도의 크기로 줄일 수 있다. 돌의 개수는 최대 1500개를 넘지 않으..