밤이 블로그

BOJ#13398 연속합2 * 문제https://www.acmicpc.net/problem/13398 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%2313398_ContinuousSum2/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#13398 연속합2 * https://www.acmicpc.net/problem/13398 */ public class Main { static final int MIN = -100000000; ..

BOJ#9376 탈옥 * 문제https://www.acmicpc.net/problem/9376ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 J번 * 풀이어려운 문제라고 생각합니다. 일단 맵을 상하좌우로 1칸씩 늘려줍니다. -> 이유 : 시도1 처럼 여러 시작점들을 어딘가에 저장해놓고 조사하는 것과, 외곽의 어느 한점을 시작점으로 잡고 조사하는 것은 차이가 없다.(문이 아니라면 cost가 없기 때문) 죄수 2명을 탈옥시키는 방법은 3가지가 있습니다. 1) 죄수 1이 죄수2를 데리고 바깥으로 나가는 경우 2) 죄수2가 죄수1을 데리고 바..

BOJ#14226 이모티콘 * 문제https://www.acmicpc.net/problem/14226 * 풀이 푸는데 고생했지만 재밌는 문제입니다.처음에는 1000개의 테스트케이스 중 11개만 틀렸는데, 원인을 찾기 쉽지 않았습니다. BFS 돌리면서 visited 배열로 정점을 중복 방문하지 않게 구현했는데, 이것이 실패 원인이었습니다. 왜냐하면 정점의 값이 같더라도 클립보드에 어떤 내용이 들어있는지에 따라 향후 탐색할 수 있는 정점이 달라지기 때문입니다. 따라서 visited 배열을 discovered 배열의 개념으로 바꾸고discovered 배열을 (기존)boolean[][] discovered = new boolean[정점] (변경)boolean[][] discovered = new boolean[..

BOJ#5014 스타트링크 * 문제https://www.acmicpc.net/problem/5014 * 풀이 생략 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%235014_Startlink/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; /** * BOJ#5014 스타트링크 * https://www.acmicpc.net/problem/5014 *..

BOJ#2468 안전 영역 * 문제https://www.acmicpc.net/problem/2468 * 풀이 비가 내리는 양을 증가시키면서 BFS 또는 DFS를 수행하면 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232468_SafetyZone/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; /** * BOJ#2468 안전영역 * https:..

BOJ#2206 벽 부수고 이동하기 * 문제https://www.acmicpc.net/problem/2206 * 풀이 BFS 또는 다익스트라로 풀 수 있습니다.벽을 부수는 경우와 벽을 부수지 않는 경우를 나누어서 진행하면 됩니다. 비슷한 문제 : 도로포장, 알고스팟 * 나의 코드 https://github.com/stack07142/BOJ/tree/master/BOJ%232206_WallDestroy/src import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Strin..

BOJ#3055 탈출 * 문제https://www.acmicpc.net/problem/3055 * 풀이BFS로 풀었습니다.map을 3차원 배열로 만들었고(행, 열, 시간)물의 위치에서 bfs 탐색, 그 이후 고슴도치 위치에서 bfs탐색하여 탈출이 가능한지 판단하였습니다. 비슷한 문제 : 5427 불 https://www.acmicpc.net/problem/5427 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%233055_Escape/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

BOJ#5214 환승 * 문제https://www.acmicpc.net/problem/5214 * 풀이 하이퍼튜브는 M개만큼 있고, 각각의 하이퍼튜브는 K개의 노드를 연결하고 있다. -> 간선 정보가 여태까지 풀어본 문제와는 다르게 주어짐-> 간선 정보를 어떤 자료구조에 어떻게 담을지 고민-> 인접 행렬은 메모리 초과 (N 각 하이퍼튜브는 최대 1000개의 노드 정보를 담고 있으므로, 이것을 일일이 짝을 맞추어가며 간선 정보를 저장하기 쉽지 않다. 생각한 아이디어는 다음과 같다.각 하이퍼튜브에 연결된 노드 정보는 아래와 같고1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 각 하이퍼튜브에 속하는 노드에 임의의 더미 노드를 생성하여 연결시킨다.10 ↔ 1, 10 ↔ 2, 10 ↔ 311 ↔ 1, 11 ..

BOJ#1520 내리막 길 * 문제https://www.acmicpc.net/problem/1520 * 풀이무심코 풀었다가 틀린 원인을 찾지 못해서 고생한 문제입니다. 주의해야 할 점으로는내리막길로 이동하다가 중간에 멈추는 경우가 생길 수 있는데이 때 dp값은 0이 되어야 할 것입니다. 그런데 dp 초기값을 0으로 설정한 경우 위 경우를 처리할 수 없어 memoization을 하지 못하고 다시 연산을 해야하므로 시간초과가 발생하게 됩니다. 따라서 dp 초기값을 위 경우(0)를 처리할 수 있는 값으로 설정해야 합니다. (예: -1) ∴ dp 초기값 설정 시 주의할 것 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231520_Downhill/src/..

BOJ#13460 째로탈출 2 * 문제https://www.acmicpc.net/problem/13460 * 풀이 dp + 탐색문제.별로 설명할 것이 없습니다. 코드 이해 안가시면 댓글 주세요. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%2313460_XHEscape/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#13460 째로탈출 * https://www.acmicpc.net/problem/13460 */ public cl..