본문 바로가기

문제 해결/BOJ117

[백준] A를 B로 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 그리디 문제입니다. 그리디 문제에 약해서 풀이까지 애를 먹었습니다. 아이디어는 간단합니다. 먼저 문자열을 정렬해서 비교했을 때 같은 문자들로 구성되어 있지 않으면 아무리 이동시켜도 만들 수 없습니다. 이제 두 문자열은 같은 문자들로 구성이 돼있음이 보장됩니다. 다음으로, 이제 A와 B의 뒤에서 부터 문자를 비교하여 같은 경우에는 이동시킬 이유가 없으므로 계속해서 버립니다. 이제 A와 B의 마지막 문자가 다르므로 A에서 이동이 필요합니다. 마지막 문.. 2023. 2. 10.
[백준] 산책(small) https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net S -> E로의 최단거리를 구해 해당 경로를 위해 사용된 정점을 제외하고 E -> S로의 최단거리를 구해주면 된다. 간선의 길이가 1으로 고정이 되어있으므로 BFS를 2번 돌려서 풀이가 가능합니다. 이 문제의 포인트는 최단 경로를 위해 사용된 노드들을 기록해야하는데 이는 S -> E를 위한 BFS를 돌릴 때 현재 노드의 이전 노드를 기록해두면 됩니다. 다음 노드를 .. 2023. 2. 10.
[백준] 원 이동하기 2 https://www.acmicpc.net/problem/22948 22948번: 원 이동하기 2 좌표평면에 원의 중심이 x축 위에 있는 $N$개의 원이 존재한다. $N$개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다. 하나의 원이 다른 원 안에 포함될 www.acmicpc.net A원과 B원 사이의 경로를 구하는 문제입니다. 먼저, 저는 크게 2가지 케이스로 나누어서 진행하였습니다. A와 B중 한쪽이 나머지 한쪽에 포함되는 경우, 그렇지 않은 경우로 나누었습니다. 1. 한쪽이 나머지 한쪽을 포함하는 경우 어느 원이 더 큰 원인지를 판별하기 위하여 반지름을 비교하게 됩니다. 만약, 도착원인 B가 더 작은 경우에는 B를 포함하고 도 큰 원들의 리스트에 시작원인 .. 2023. 2. 9.
[백준] 뉴스 전하기 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제를 제대로 파악하는데 시간이 걸린 문제입니다. 처음에는 단순 BFS로 접근했다가 부하 직원에게 동시에 통화가 불가능하다는 조건을 깨닫고는 풀이를 1차 변경, 간접 상사 직원도 통화가 가능하다고 생각했는데 직속 부하 직원에게만 통화가 가능하다고 해서 2차 풀이 변경, 무조건 현재 노드를 루트로 하는 서브트리의 노드 개수가 많은 노드부터 BFS로 탐색하는 풀이로 진행했다가 마지막으로 각각의 서브트리에서.. 2023. 2. 8.
[백준] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 3차원 배열을 이용하여 BFS를 해야하는 문제입니다. 단순하게 [벽을 부쉈는지 여부][y][x]로 정의하고 각각의 상태에서 가질 수 있는 최소 거리를 저장해두면 된다. 즉, 벽을 부수고 도달할 수 있는 최단거리와 벽을 부수지 않고 도달할 수 있는 최단 거리중 더 짧은 거리를 답으로 출력하면 된다. import sys from collections import deque i.. 2023. 2. 7.
[백준] 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net Deque를 활용한 구현, 시뮬레이션 문제입니다. 지문을 제멋대로 해석하는 바람에 살짝 해맸던 문제입니다. 회전한 다음 지워진 숫자가 없는 경우 평균을 구해 더하거나 빼는 작업을 진행해야하는데 각 원판별로 체크를 해서 진행하는 줄 알았는데 원판 전체에 대해 지워진 경우가 없을 때에만 작업을 해줘야합니다. 그리고 x배수의 원판을 회전시켜야하는데 이부분에서 실수가 있었습니다. 포인트가.. 2023. 2. 7.
[백준] 두 배 더하기 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 배열의 모든 요소들을 0으로 만드는 최소횟수를 구하는 방식으로 바꿔서 생각해보면 편하다. 최소횟수가 되기 위해서는 나누기 연산을 최대한 활용해야하는데 그렇게 하기 위해서 nums의 모든 요소들을 짝수로 만들어주고 나누기를 진행해주면 된다. # 문제링크: https://www.acmicpc.net/problem/12931 import sys input = sys.stdin.readl.. 2023. 2. 6.
[백준] 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 통해 +1, -1, 순간이동(X2)를 통해 도달할 수 있는 모든 경우를 체크해주었습니다. 우선순위 큐를 활용하여 cnt가 낮은 상태가 먼저 나오도록 하여 현재 숫자에 도달할 수 있는 가장 적은 횟수가 visited에 저장되도록 하였습니다. 그 다음으로는 순서를 정하는 방법입니다. K를 시작으로 +1을 통해 도달한 경우, -1을 통해 도달한 경우, 순간이동.. 2023. 2. 6.
[백준] 군사 이동 https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 경로에 존재하는 가장 넓은 너비를 구하는 것이 목적인 문제입니다. 지나갈 수 있는 최소 너비를 지정해주고 이보다 큰 간선만을 택하면서 다익스트라를 수행한 다음 목적지에 도달할 수 있는지를 체크하면 풀 수 있습니다. # 문제링크: https://www.acmicpc.net/problem/11085 import sys, os, heapq from c.. 2023. 2. 5.

티스토리툴바