나그네

17071번: 숨바꼭질 5 문제 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 수빈이(편의상 누나)는 다른 숨바꼭질 문제들처럼 +1, -1, ×2로 이동 가능하고 시간은 1초 걸린다. 대신 동생이 1초에 1칸, 2초에 2칸,... N초에 N칸씩 움직인다. 따라서 BFS 알고리즘을 사용해서 풀 수 있다. 처음 접근 방식은 각각에 대해 BFS를 하며 (동생은 사실 하나만 이동하지만) 시간 단위로 이동하고..

1543번: 문서 검색 문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 문서와 단어를 입력받아 문서 내에 단어를 중복되지 않게 몇 개 셀 수 있는지 구하는 문제다. 문서의 가장 처음 인덱스(0)부터 단어와 비교를 하고 다르면 다음 index로 넘어간다. 만약 단어를 찾으면 카운트를 증가시키고 다음 탐색할 문서의 위치를 현재 위치에서 단어의 길이만큼 더해준다. 코드 #include using namespace std; int main() {..

1463번: 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍(DP)으로 해결할 수 있는 문제다. 할 수 있는 연산은 아래와 같다. 3으로 나누어 떨어지면 3으로 나누기 2로 나누어떨어지면 2로 나누기 1 빼기 bottom-up 방식으로 구현했다. 1은 0번의 연산으로 1을 만들 수 있다. 2 이상의 수는 기본적으로 i번째 수는 이전 수에서 1을 더한 수이므로 dp[i] = dp[i-1] + 1이다. 만약, i번째 수가 3의 배수라면 i/3에서 3을 곱한 수일 것이다. 따라서 dp[i] = dp[i/3] + 1일 '수..

1456번: 거의 소수 문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 풀이 거의 소수는 소수의 N제곱 형태인 수를 말한다. 범위 내 거의 소수의 개수를 구하는 문제다. 수의 범위가 10^14이고 N제곱 형태를 구하므로 에라토스테네스의 체를 사용해 10^7까지의 소수만 구해준다. 소수를 i라고 한다면 i^2 = i × i부터 범위에 포함된다면 카운트를 증가시켜 주면 된다. 단, 범위 판단에 주의해야한다. 현재 수의 +1승이 범위 내인지 확인하려면 (..

1436번: 영화감독 숌 문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 풀이 666이 들어간 수를 종말의 숫자라 한다. 수를 증가시켜 가며 수에 종말의 숫자인지 확인한다. N번째 종말의 숫자를 출력하는 문제다. 1000으로 나눈 나머지가 666이면 카운트를 증가시키고 다음 수를 확인한다. 666이 아니라면 10으로 나눠주어 마지막 자리 수를 버리고 다시 탐색한다. 이를 0이 될 때까지 반복해 종말의 숫자인지 확인한다. 코드 #inclu..

27648번: 증가 배열 만들기 문제 https://www.acmicpc.net/problem/27648 27648번: 증가 배열 만들기 첫째 줄에 $N$, $M$, $K$가 주어진다. $\left(1 \le N , M \le 1\,000,1 \le K \le 100\,000 \right)$ www.acmicpc.net 풀이 맨 왼쪽 위부터 맨 오른쪽 아래 칸까지 이동하는데 각 칸의 수가 증가하도록 구성해야 한다. 이 배열을 만들 수 있는지 여부와 만들 수 있다면 가능한 것 중 하나를 출력하면 된다. 대각선을 왼쪽 위부터 오른쪽으로 차례대로 1, 2, 3,...으로 증가시키도록 구성하면 된다. ex) 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 실제 배열을 만들 필요도 없이 출력할 수 있다. 맨..

12020번: LU 분해 문제 https://www.acmicpc.net/problem/12020 12020번: LU 분해 \(N \times N\) Matrix A가 주어진다. LU 분해란 \(A = LU\)꼴의 Matrix 곱로 분해하는 것이다. (단, \(L\)은 Lower Triangular Matrix, \(U\)는 Upper Triangular Matrix) Lower Triangular Matrix란 \(L_{ij} = 0 \text{ (if }i < j\text{)}\) Upper www.acmicpc.net 풀이 선형대수학에서 배우는 LU 분해를 구현하는 문제다. 구현 자체는 LU 분해를 하는 방식대로 하면 된다. LU 분해에 대해선 설명 잘해놓은 다른 블로그를 참고하는 게 좋을 것 같다..

4179번: 불! 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 재민이가 불을 피해 가장자리로 가서 탈출할 수 있으면 탈출하는 최단 시간을, 탈출할 수 없으면 IMPOSSIBLE을 출력하는 문제다. 틀린 풀이 BFS를 시작할 때 재민이는 1부터 시작하고 불은 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음 불이 이동하도록 했다. 이동할 때마다 visited 배열 값이 1씩 증가하도록 해서 시간을 계산했다. 큐..

5719번: 거의 최단 경로 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다. [다익스트라 알고리즘 알아보기] 먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 ..

1188번: 음식 평론가 문제 https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 소시지의 개수 N과 평론가의 수 M을 입력받고 소시지 N개를 모두 균등하게 나누어 평론가 M명에게 같은 양을 나누어 준다. 이때 소시지를 자르는 횟수를 구하는 문제다. 소시지를 일자로 세우고 M등분하면 된다. 이때 칼질의 횟수는 M-1번이 된다. 그러나 이미 소시지는 N개를 일자로 나열한 것이므로 N등분되어있다. 따라서 중복으로 잘리는 횟수를 구해 빼주면 된다. 중복인 칼질의 수는 (N과 M의 최대공약수) - 1 이므로 정답은 M - gcd(N, M)이다. 코드 #..