나그네

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를 진행한 횟수가 정..

1011번: Fly me to the Alpha Centauri 문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 문제에서 출발과 도착하기 바로 직전의 이동거리는 1광년만 이동가능하다. 가장 먼저 작동 횟수의 최솟값이기 때문에 이동 거리는 점점 커지다가 줄어야 한다고 생각했다. 출발점과 도착점에서 거리가 1씩 커지면서 출발한다고 생각했고 두 지점 간 거리가 양수인 동안 먼저 (두 지점 간 거..

1010번: 다리 놓기 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 서쪽의 사이트 개수 N, 동쪽의 사이트 개수 M을 입력받고 두 사이트를 잇는 경우의 수를 구하는 문제다. 조합을 사용하면 쉽게 풀 수 있다. nCr(조합): n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수 (단, 중복은 불가능) nCr = nPr / r! n*(n-1)*(n-2)*...*(n-r+1) 즉, nCr = ──────────── 이다. r*(r..

17087번: 숨바꼭질 6 문제 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 풀이 수빈이는 좌우로 D칸씩 이동할 수 있고 모든 동생을 찾기 위한 D의 최댓값을 찾는 문제다. 즉, 모든 수빈이와 동생 사이의 거리의 최대공약수를 구하는 문제다. 먼저 첫 번째 동생과의 거리를 D라 하자. 다음 동생의 위치를 입력받을 때마다 입력받은 동생과의 거리와 D의 최대공약수를 D에 저장한다. 따라서 D를 출력하면 정답이다. ..