문제 풀이19 [백준] 20926번 - 얼음 미로 (Java) 문제 https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 입력 출력 알고리즘 다익스트라, 구현 최단 시간을 물어봤으므로 그냥 BFS를 쓰면 되는거 아닌가라고 생각할 수 있지만, 각 칸에 가중치가 존재하므로 이 문제는 BFS로 풀 수 없다. 모든 가중치가 양수이므로 다익스트라로 최단 경로를 구하면 된다. 일반 다익스트라랑 똑같이, 2차원 배열의 다익스트라 구현 문제라고 생각하면 된다. 풀이 과정은 아래와 같다. 1. 그래프 탐색하는 것 처럼 방향벡터를 .. 2023. 12. 5. [백준] 9370번 - 미확인 도착지 (Java) 문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 입력 출력 알고리즘 다익스트라 문제를 요약하자면 시작지점 s로 부터 t개의 목적지 후보까지 g-h 간선을 포함해서 갈 수 있는 목적지 후보만 출력하는 것이다. 두가지 방법으로 풀어볼 것이다. [ 방법 1 ] 우리가 체크해야 할 것은 s → 목적지 후보까지 가는 최단 경로에 g → h 또는 h → g가 포함되어 있는가이다. 따라서 모든 목적지 후보에 대해서 s →목적지까지 바로 가는 최단.. 2023. 12. 4. [백준] 17836번 - 공주님을 구해라! (Java) 문제 https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 입력 출력 알고리즘 너비 우선 탐색(BFS) 일단, 최단 시간을 물어봤으므로 항상 최단경로를 보장하는 BFS로 무조건 풀어야 한다. DFS로는 이 문제를 풀 수 없다. 그람을 구해서 벽을 부수고 가는 것이 최단경로일 수도 있고, 그람을 안구하고 돌아서 가는 것이 최선일 수도 있다. 또한, 사방이 벽으로 막혀 있어 반드시 그람을 구하고 가야되는 경우도 존재한다. 따라서, 그람을.. 2023. 12. 4. [백준] 21475번 - Треугольная рамка (Java) 문제 https://www.acmicpc.net/problem/21475 21475번: Треугольная рамка Входной файл содержит четыре целых числа $a$, $b$, $c$, $d$ ($1 \le a, b, c, d \le 1000$) --- длины внешних сторон рамки и ее ширину, соответственно. Гарантируетс www.acmicpc.net 입력 출력 번역본 https://www.acmicpc.net/board/view/115980 글 읽기 - 이 문제에 대한 번역입니다. 참고하세요 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 알고리즘 수학, 기하학 일단 문제에서 예시로 직각 삼각형인거마.. 2023. 12. 4. [백준] 2342번 - Dance Dance Revolution (Java) 문제 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 입력 출력 알고리즘 다이나믹 프로그래밍 각 쿼리처리 시점에서 왼발과 오른발 위치에 따른 힘의 최솟값을 계속 기록해두고 출력하면 된다. dp[i][j][k] : i번째 DDR 쿼리를 처리하는 시점에서, 왼발이 j에 있고 오른발이 k에 있을때 힘의 최솟값 이라고 dp테이블을 정의해보자. 여기에 쿼리가 아래와 같이 주어진다고 예시를 들어보자 1 2 2 4 0 쿼리.. 2023. 12. 4. [백준] 18235번 - 지금 만나러 갑니다 (Java) 문제 https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net 입력 출력 알고리즘 너비우선탐색(BFS) 일단 만날 수 있는 "최소 일수"를 물어봤다. 즉, 최단 경로를 물어본 것이다. 따라서 이 문제는 깊이우선탐색(DFS)로 풀 수 없다. 최단 경로를 보장하는 것은 BFS이기 때문이다. 찾아보니깐 비트마스킹으로 푸는 사람들도 있지만 그냥 더 단순하고 직관적인 풀이로 설명하겠다. 일단 처음에는 특정 지점에 몇일에 도착하는지 기록할 배열을 하나 만든다. 이때, 위치는 최대 n까지이라고 했으므로 배열의 크기는 n+1로 .. 2023. 12. 3. [백준] 15311번 - 약팔기 (Java) 문제 https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 입력 출력 알고리즘 수학, 애드 훅, 해 구성하기 문제를 보자마자 모든 값을 커버해야 되니깐 이진수를 쓰면 되지 않나..? 라고 생각할 수 있다. 하지만 이 문제에는 함정이 있다. 반드시 연속된 자리에 있어야되기 때문이다. 따라서 이 방법으로 풀 수 없다. 이 문제는 입력이며 예제며 되게 거창하게 주어져있는데 싹다 함정이다. 다 필요없다. n = 1000000이 될때까지 다 커버할 수 있게 약봉지를 만들어두면 n값에 관계없이 답은 동일하게 나온다. 그냥 1개씩 든 약봉지를 10.. 2023. 12. 2. 이전 1 2 3 다음
