YANGORITHM

문제 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net 풀이 브루트포스로 해결하면 시간초과가 발생한다. 먼저 x를 맞춰주고 그 후에 y를 찾아줘야 한다. 1. x는 M만큼 증가를 한다. 따라서 x = x ..

문제 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 높이에 따라 세 가지 경우로 나누어서 풀어야 한다. 1. 높이가 1인 경우 나이트는 이동할 수 없다. 2. 높이가 2인 경우 위로1칸 오른쪽 2칸, 밑으로 1칸 오른쪽 2칸 으로만 이동할 수 있다. 3. 높이가 3 이상인 경우 가로 길이가 7을 기준으로 나누면 된다. 높이가 2인 경우 이동가능한 방법으로 이동할 수 있는 최대 이동 횟수는 3번이다. 이동 횟수 4번 부터는 4가지 이동 방법을 모두 사용해야 하므로 3번까지만 이동할 수 있다. 높이가 3이..

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 d[k][n]을 k개를 이용해 n을 만든다고 가정한다. k개의 원 ○ + ○ + ○ + ... + ● = N 이라고 한다. ●에 올 수 있는 수 i는 0부터 N까지이다. 그러면 다음과 같은 점화식을 만들 수 있다. d[k][n] = d[k-1][n-i] (i = 0~n) 이 점화식을 이용해 문제를 해결한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include using namespace s..

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으 www.acmicpc.net 풀이 (1,1)에서 (N,M)까지 이동해야 하는 문제이고 이동가능한 방향은 오른쪽, 아래, 오른쪽 대각선 아래 방향 세 가지 경..

문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 풀이 스택을 이용해서 폭발 문자열과 관련된 인덱스를 저장하고 erase 배열에는 폭발할 문자열의 인덱스를 체크한다. 문자열과 폭..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 풀이 n번째 줄까지 값을 더했을 때 최대값을 찾아야하는 문제이다. i번째 줄에서 선택할 수 있는 숫자는 i-1번째에 있는 숫자들 ..

문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 수열을 확인하기 위해 스택을 이용해서 해결하는 문제이다. 스택은 top에 값만 확인할 수 있는 성질을 이용하면 문제를 해결할 수 있다. 만약 스택에 현재 입력된 숫자가 없다면 스택의 top이 현재 입력된 숫자까지 되도록 수들을 push한다. push 순서는 오름차순이므로 순서대로 숫자를 넣어주면 된다. 만..

문제 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net 풀이 10의 배수들이 끝자리가 0이 된다. 10은 2x5로 이루어진다. 따라서 조합의 결과 값에서 2와 5의 개수를 구하면 된다. 2와 5의 각 개수 중 적은 값이 만들 수 있는 0의 수가 된다. nCm = n! / (m! * (n-m)!) 이므로 nCm을 한 이후에 2와 5의 개수를 구하면은 시간초과가 발생한다. 따라서 각각을 따로 구한다. 1. n!에서 2, 5의 개수 2. m!에서 2, 5의 개수 3. (n-m)!에서 2, 5의 개수 1번에서 2, 3번에 대해 각각 뺄셈을 진행한 후에 2..

문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모 www.acmicpc.net 풀이 에라토스테네스의 체를 이용해서 1000000 이하의 소수를 먼저 구한다. 에라토스테네스의 체를 이용하면 c 배열에 각 ..

문제 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 풀이 pair와 vector를 이용해서 입력 값을 저장한다. pair에 인덱스와 움직일 숫자를 넣어서 vector에 저장을 한다. 그 다음 부터는 vector에 맨 앞에 저장되어 있는 값을 출력하고 바꿔주면 된다. 움직일 숫자가 양수이면 vector의 앞에 있는 값을 뒤로 보내주고, 음수면 vector의 뒤에 있는 값을 앞에 넣어준다. 1. vector의 front 값의 인덱스를 출력 후 삭제 2. front 값의 움직일..