📚 문제 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 🔍 아이디어 구현문제로 반례를 잘 생각해야 하는 문제인 것 같다. 방향을 문자로 입력받아서 이 부분을 enum으로 처리했는데 hash 등을 이용하는 방법이 더 빠를 것 같다. 또한, 행과 열의 순서와 이동할때의방향을 고려해서 문제를 풀어야 한다(헷갈린다..) 또한 행은 감소하는 방향으로 1~8까지 있지만 열을 A~H로 [1,8] , [A, H] 범위를 체크해야 한다. 풀이순서. 1. 킹을 움직이고 킹의 이동이 범위를 넘어간 경우 넘어간다. 2. 킹이 움직인 위치가..
📚 문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 🔍 아이디어 배열의 사이즈가 작아서 그냥 배열로 저장하여 찾는 방법을 선택하였다. 해당문제에서 시간 초과가 나는 포인트는 상어의 속도라고 판단하여 해당 부분을 따로 처리해 주었다. 상어의 방향이 오른쪽 왼쪽인 경우, 위아래인 경우를 따로 처리하였다. 먼저 오른쪽, 아래쪽인 경우는 velocity만큼 더하고 , 왼쪽 위쪽인 경우에는 velocity만큼 뺀다. 만약 위 아..
📚 문제 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 🔍 아이디어 처음 문제를 봤을 때는 그냥 dfs를 이용하는 풀이를 생각했다 -> 그래서 3번 시간 초과 났다 (dfs에서도 최적화 가능한 줄 알고 여러 번 도전했다.) 3번이나 시간초과 후에는 dp를 떠올렸다. 생각해보니까 가능하다는 생각이 들었다. 그래서 dp로 수정하고 제출하니까 16%에서 틀렸습니다 라는 메시지가 나와서 당황했다. 뭐지.. 설마 타입문제인가 라는 생각으로 엣지 케이스를 넣으니까 음수로 나와서 오버플로우발생을 확인했다 이후에 long으로 선언..
📚 문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 🔍 아이디어 기본적인 구현 문제이다. DFS/ BFS 두 가지로 모두 풀 수 있지만 나는 BFS를 이용해서 풀이하였다. 갈 수 있는 길이 대각선을 포함함으로 경로에 추가한다. 또한 모든 섬을 찾아야 하기에 모든 배열을 탐색하면서 이미 방문하지 않은 섬의 경우에 탐색을 시작하고 해당섬을 BFS로 순회하면서 visit 배열을 색칠하면 된다.(방문처리를 한다) 즉, 모든 지도를 탐색하면서 1번 섬을 만난 경우 1번 섬에 대해 visit을 모두 칠하고, ..
📚 문제 https://www.acmicpc.net/problem/1092 🔍 아이디어 크래인을 효율적으로 사용하는 것이 중요하다고 생각했습니다. 한 크래인이 실을 수 있는 물건들중 가장 무거운 물건을 선택한다면 가장 효율적으로 크래인을 사용하여 모든 화물을 실을 수 있을것이라 판단하여 이분 탐색을 이용하여 크래인이 실을 수 있는 무게 N보다 작은 수중 가장 큰 숫자를 선택했습니다. -1이 나오는 경우는 크래인의 옮길 수 있는 가장 큰 허용량 보다 무거운 화물이 있는경우이기에 sort를 이용하여 정렬후에 비교하였습니다. 이분탐색에서 어떤 한 숫자보다 작은 수중에 가장 큰 수는 아래와 같은 로직으로 해결할 수 있습니다 crane이 실을 수 있는 경우 result를 갱신합니다. //이분탐색은 정렬되어있어야 ..
📚 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 🔍 아이디어 📝 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR..
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class boj_3015_오아시스재결합 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); long sum = 0; Stack stack = new Stack(); //스택에는 점점 작아지는 순으로 사람을 넣는다 for (i..
