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

1. 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 풀이 과정 처음엔 ArrayList로 구현했다가 N의 범위가 100보다 작아서 2차원 배열이 더 빠를 것 같아서 수정했더니 2배 빨라졌다. 배열의 처음과 끝이 이어져있기 때문에 1번 과정에서의 8방향 탐색은 나머지 연산을 활용했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

1. 문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 2. 풀이 과정 상근이가 이미 지나간 곳은 불이 번져도 상근이를 따라 잡을 수 없기 때문에, 불이 번지는 건 빈칸만 고려해주었다. 빈칸을 누가 먼저 가냐만 보면 된다. 상근이가 현재 갈 수 있는 위치와 불이 방금 번진 위치를 모두 queue에 넣고, 4방향 탐색으로 갈 수 있는 곳에 표시를 해준다. 이때, 상근이는 불이 다 번지고 난 후에 움직이기 때문에 처음 상근이의 위치는 queue의 마지막에 ..

1. 문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 2. 풀이 과정 손에 든 계란으로 어떤 계란을 칠 지에 따라 DFS탐색을 한다. DFS가 끝나면 다른 길 탐색을 위해, 이전에 바꿔준 변수를 되돌려준다. 이때 주의할 점은 두 가지였다. 여기서 자기 자신은 깰 수 없다는 것과 손에 든 계란이 깨질 경우와 친 계란이 깨질 경우를 모두 고려해서 cnt를 증가시켜야 한다는 점이다. import java.io.BufferedRea..

1. 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 2. 풀이 과정 2차원 배열을 탐색하면서 1을 찾으면, DFS를 이용하여 4방향에 이어진 값들을 찾으며 탐색한 값의 개수가 몇 개인지 전역변수인 size를 이용하여 연산했다. 방문 체크는 2차원 배열의 값을 0으로 바꿈으로써 확인해준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Strin..

1. 문제 https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net 2. 풀이 과정 시간을 ":"을 기준으로 잘라서 int로 변환하여 분단위로 비교하였다. 시작시간보다 빨리 채팅을 친 사람들을 Set에 넣으며 중복 제거를 함께 해주었다. 종료시간과 스트리밍 종료시간 사이에 채팅을 친 사람은 Set에서 빼주면서 결과값을 구하였다. 추가적으로 입력이 언제 종료되는지 모르기 때문에, EOF검사를 해주어야 한다. Scann..

1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 과정 보통 DFS, BFS를 같이 쓸 수 있는 문제가 많아서 대부분 DFS로 풀다가 이번에 오랜만에 BFS 방식으로 풀어서 어색했다. 가능한 경로 중에서 최소 길이를 찾는 문제라서 BFS 방식으로 풀어야 한다. 풀이 방식을 간단하게 설명하면, Queue에 방문할 수 있는 층수를 넣고 Queue의 크기만큼 반복문을 돌며 다음 단계에 방문할 수 있는 층을 찾는다. 이미 방문한 층은 다시 방문..

1. 문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 과정 가로, 세로 따로 보고 겹치는지 확인해주면 된다. 즉 각 길간에는 경사로가 겹치는지는 확인할 필요 없다. 경사로로 갈 수 있는지는 1칸 오르막 길과 1칸 내리막 길 2가지 경우로 나눠서 생각해줬다. '오르막길'의 경우, 길 하나를 탐색하면서 현재 보고 있는 값과 같은 값이 몇 개 연속으로 나왔는지 저장하고 있다가 오르막길을 만났을 때 그 개수가 L개 이상이면 pass, 아니면 return fa..

1. 문제 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 2. 풀이 과정 DFS, BFS 탐색 문제인데, 고민했던 부분은 방문체크를 어떻게 할 지였다. 방문체크는 A, B에 부었던 물의 양으로 2차원 배열을 사용했다. A, B의 물의 양이 정해지면 C의 물의 양도 정해지기 때문에, 2차원 배열로 물통들의 상태를 방문 체크 해줄 수 있다. 아래 푼 방식은 DFS를 사용했다. A에 있는 물의 양이 0보다 크다면 B, C 각각 ..

1. 문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 풀이 과정 처음에 문제를 이해하는 게 제일 어려웠다. 결국 처음 풀 때는 문제를 완전히 이해하지 못하고 풀어 비효율적인 풀이였지만 통과는 했었다. 헷갈렸던 부분은 두 가지였다. 첫 번째는 컨베이어 벨트의 번호는 컨베이어 벨트가 회전할 때 같이 움직이는 것이고, 올리는 위치 내리는 위치는 그림 속처럼 시작점부터 0번째 N번째 위치를 의미한다. 두 번째는 로봇이 ..

1. 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 풀이과정 1. 중복된 수가 들어오지 않으므로, 1차원 배열에 값이 있는지 여부를 기록한다. 2. 배열의 index는 절댓값이 1_000_000이하이기 때문에, 음수도 가능하므로 (들어온 값) + 1_000_000으로 하여 값을 true로 바꿔준다. 3. 출력할 때, 배열을 처음부터 끝까지 돌면서 true면 (index값) - 1_000_000하여 결과를 출력한다. imp..