나그네

1075번: 나누기 문제 https://www.acmicpc.net/problem/1075 1075번: 나누기 첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. F는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 100 이상의 정수 N을 입력받고 100 미만의 F를 입력받아 N의 뒤에서부터 두 자리를 바꾸어 F로 나누어 떨어지게 하는 문제다. 뒤에 두 자리가 최솟값이 되도록 해야 하므로 00부터 증가시켜 가며 탐색하면 된다. N의 뒤에서부터 두 자리를 0으로 바꾼다. (N을 100으로 나눈 나머지를 N에서 뺀다.) for문을 사용해 0부터 99까지 N에 더해가며 F로 나누어떨어지는지 확인한다. 나누어 떨어..

1065번: 한수 문제 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 어떤 수 X의 각 자릿수가 등차수열을 이루면 이 수를 한수라 한다. 1000 이하의 자연수 N을 입력받고 N 이하의 자연수 중 한수의 개수를 출력하는 문제다. 100 이하 즉, 한자리 수와 두 자릿수는 어떤 상황에서도 등차수열을 이룬다. 그리고 입력되는 N은 1000 이하의 수이기 때문에 1000은 한수가 아니므로 세 자리 수만 신경 쓰면 된다. 따라서 세 자릿수를 문자열..

1041번: 주사위 문제 https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이 주사위 각 면의 숫자를 입력받고 주사위들로 N×N×N 크기의 정육면체를 만든다. 이 정육면체는 탁자 위에 있어 5면만 보이는데 이때 보이는 수들의 합의 최솟값을 구하는 문제다. '그리디하게 풀어보자' 했는데, 최대한 한 면에 작은 수를 넣고자 했고 두 면이 노출되는 경우에도 최솟값을, 세 면이 노출되는 경우에도 가능한 최솟값을 넣어줬다. 그림으..

9461번: 파도반 수열 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 한 변의 길이가 1인 정삼각형으로 시작해 도형의 가장 긴 변의 길이를 한 변의 길이로 하는 정삼각형을 추가해가며 N번째 정삼각형의 한 변의 길이를 P(N)이라 하고 이를 출력하는 문제. 1번 풀이 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 라는 문제 본문을 읽고 가장 먼저 [1, 1, 1]로 시작하며 i번째 ..

11660번: 구간 합 구하기 5 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 2차원 배열에서 (x1, y1)부터 (x2, y2)의 합을 출력하는 문제다. 가장 먼저 떠오른 생각은 행 별로 누적 합(prefix sum)을 먼저 구하는 것이었다. 이후 x1, y1, x2, y2를 입력받고 각 행별로(x1, ... , x2) 열의 누적 합(sum[y2] - sum[y1 - 1])을 답에 더해..

1037번: 약수 문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 풀이 어떤 수의 1과 자기 자신을 제외한 모든 약수를 입력받고 어떤 수를 출력하는 문제다. 약수의 최솟값과 최댓값을 곱하면 그 수가 되는 점을 이용한다. N개의 수를 입력받아 배열에 넣는다. 배열을 오름차순으로 정렬한다. 배열의 첫 번째 원소와 마지막 원소를 곱해 출력한다. 코드 #include using namespace std; int main() { ios::s..

1032번: 명령 프롬프트 문제 https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 풀이 입력받은 문자열들 중 공통되는 문자만 출력하고 나머지는 ?로 출력하는 문제다. 모든 문자열을 입력받아 배열에 넣어준다. for문으로 첫 번째 문자열의 각 index의 문자를 나머지 문자열들의 같은 index의 문자와 비교한다. 모든 문자열에서 해당 index에 문제가 없다면 그 문자를 정답 배열에 추가한다. 한 번이라도 다르다면 for문을 탈출하고 정답 ..

1021번: 회전하는 큐 문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 자료구조인 덱을 사용해 원형 큐에서 M개의 수를 꺼내는 데 걸리는 최소 횟수를 구하는 문제다. 좌, 우로 움직일 수 있고 가장 앞 원소(front)를 꺼낼 때는 횟수가 증가하지 않는다는 특징이 있다. 1부터 N을 덱에 넣는다. 찾아야 하는 수를 확인한다. 왼쪽부터 꺼내는 경우와 오른쪽부터 꺼내는 경우 중 빠른 경로를 찾는다. 빠른 방향으로 원소를 찾을 때까지..

1018번: 체스판 다시 칠하기 문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 입력받은 체스판을 8×8 사이즈로 잘라 올바르게 되기 위해 색칠해야할 가장 적은 횟수를 출력하는 문제. 브루트포스(Brute Force) 문제로 가능한 모든 경우의 수를 계산해본 후 가장 작은 값을 출력하면 된다. 체크할 경우는 흰색으로 시작하는 경우와 검은색으로 시작하는 두가지 밖에 없다. 따라서 이 보드들을 string 배열로 만들어놓으면 된다..

1012번: 유기농 배추 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 잘 알려진 bfs 문제. M×N 배열을 모두 돌면서 값이 1인 동시에 아직 방문하지 않은 점들에 대해 bfs를 시행한다. bfs에선 해당 좌표를 방문처리한 후 상하좌우를 하나씩 체크하며 값이 1인 동시에 아직 방문하지 않았다면 큐에 추가해 준다. 위 방법을 큐가 빌 때까지 반복한다. bfs를 한 번 진행하면 인접해있는 모든 배추는 방문하게 되므로, bfs를 진행한 횟수가 정..