컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 해결 알고리즘 $$ \begin{array} ddp[0][i] & = & arr[0][i] + maximum(dp[1][i-1], \; dp[1][i-2]) \\ dp[1][i] & = & arr[1][i] + maximum(dp[0][i-1], \; dp[0][i-2]) \end{array} $$ 위의 식대로 다이나믹 프로그래밍을 진행해주는 문제. 이 때 $i$는 2보다 크거나 ..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해결 알고리즘 처음 집의 색을 정해놓고 시작한다. 이때, 색칠할 색이 아닌 색은 최댓값으로 설정해두고 다이나믹 프로그래밍을 해준다. 소스 코드 #include #include using namespace std; int arr[1002][3]; int dp[1002][3]; int main(){ int N; cin >> N; int result = 1000 * 1..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해결 알고리즘 https://kimmessi.tistory.com/90 위의 문제와 풀이가 똑같다. 수의 제곱수의 최소 개수를 구할 때 그 수에서 제곱수만큼 뺀 숫자들 중에서 제곱수의 개수가 최소인 수의 제곱수의 개수에서 +1 한 만큼의 값을 입력해준다. 답을 구할 때까지 계속 반복 후 N까지 구했을 때 출력해준다. 소스 코드 #include using n..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 해결 알고리즘 수의 제곱수의 최소 개수를 구할 때 그 수에서 제곱수만큼 뺀 숫자들 중에서 제곱수의 개수가 최소인 수의 제곱수의 개수에서 +1 한 만큼의 값을 입력해준다. 답을 구할 때까지 계속 반복 후 N까지 구했을 때 출력해준다. 소스 코드 #include using namespace std; int dp[100002]; int main(){ int ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 문제 해결 동적계획법(다이나믹 프로그래밍)을 쓰는 문제 연속된 세 개의 계단을 밟을 수 없으므로 이차배열을 선언해준다. 연속으로 밟은 계단의 갯수를 배열로 알 수 있게 설정한다. 만약 2개의 계단을 밟았을 경우 두 칸을 넘게 한다. 반복문이 끝난 후, 마지막으로 N번째 행에서 최댓값을 구해서 출력한다. 소스 코드 #include using namespace std; int main(){ int N; ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 해결 알고리즘 전형적인 다이나믹 프로그래밍 문제 삼각형이란 것만 유의 해주어 각각의 양쪽 대각선 위의 값 중 최대값에 원래 있던 값을 더해주는 과정을 반복해주어 마지막 행에서 가장 큰 수를 출력해주면 된다. 소스 코드 #include using namespace std; int dp[502][502]; int main(){ int n; cin >> n; for(int i=1;i k; if(i == 1) dp[i][j] = k; else { if(j != 1) dp..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍으로 푸는 문제였다. 푸는 방식은 아래 링크에 자세하게 나와 있다. https://kimmessi.tistory.com/65?category=871925 [알고리즘] 동적계획 - 이항계수, 플로이드-와샬, 연쇄행렬곱셈 동적계획 알고리즘이란? 동적계획은 분할한 입력사례를 재귀 호출해 답을 얻고, 그 보다 작은 입력사례의 답을 먼저 구해 저장해놓고, ..

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 이용하면 쉽게 풀리는 문제이다. 배열(dp)를 선언해주고, 이 배열에 첫째 행은 2x1 타일이 마지막에 올 때 개수이고 두번째 행은 1x2타일이 마지막에 올 때 개수이다. 2x1이 마지막에 올 때는 1개만 와도 직사각형이 다 차기 때문에 1행만 비어있어도 하므로 1행 전에 있는 개수들을 더해준다. 1x2이 마지막에 올 때는 2개가 있어야 직사각형이 다 차기 때문에 2행이 비어있어야 하므로 2..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 해결 알고리즘 이 문제는 다이나믹 프로그래밍으로만 풀면 메모리초과가 나는 문제였다. 그래서 나머지를 쓰는 방식으로 문제를 풀어가면 메모리 초과를 피해갈 수 있다. 1. 첫 줄의 입력을 우선적으로 배열(dp, dp2)에 입력 받는다. 이 두개의 배열은 각각 최소, 최대 값을 계산하기 위해 나눈 것이다. 2. 배열에 위칸에서 내려올 수 있는 값들 중 최소, 최대 값에 입력 받은 수를 더해서 다음 열을 구성해준다. 이때, 배..

www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 해결 알고리즘 문제의 다리 놓기의 경우의 수는 사실 조합과 같다. 그렇기 때문에 $_{1}C_{1}$부터 $_{30}C_{30}$의 값을 배열에 넣고 입력 값에 대한 조합 값을 출력해주면 된다. 1. 우선 배열에 모든 조합 값을 다 넣어준다. 이때 입력 값이 너무 크면 오버플로우가 생길 수 있으므로 배열은 long long 으로 선언해주어야한다. 또, 동쪽과 서쪽의 사이트가 바뀌어도 경우의 수가 같으므로 ..