MoonBug

> https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 좀 애를 먹었던 문제 나는 1~9로 시작하는 수로 숫자를 세어보려 했는데, 0~9로 끝나는 숫자의 수를 저장하고 다음 턴에서 뭐 3으로 끝나는 수를 구하고 싶으면 1. 4에서 끝나는 수 뒤에 3 붙이기 2. 2에서 끝나는 수 뒤에 3 붙이기 그래서 [i][3] = [i-1][2] + [i-1][4] 이런 식으로 점화식을 구성해야 한다. > #include using namespace std; long long arr[100][10]; int main() { int num; cin >> num; arr[0][..

C++/Baekjoon 2024. 1. 29. 02:04

> https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP를 이용한 문제입니다. 10이 주어졌을 때, 우리는 3가지만 비교해보면 됩니다. 1. 3으로 나눈 경우 => 나누어 떨어지지 않기에 패스 2. 2로 나눈 경우 => 5 -> 5의 최소값을 알아야 함 3. 1을 뺀 경우 => 9 -> 9의 최소값을 알아야 함 이렇다면 5의 최소값과 9의 최소값을 비교해야 하는 상황이 나옵니다. 그럼 5의 최소값과 9의 최소값을 알고 있는 편이 좋겠죠? 이를 위해서 1부터 입력받은 숫자까지 최소값을 채워나가면서 배열에 저장합니다. 그럼 배열의 한 칸을 채울때 3가지 경우만 ..

C++/Baekjoon 2024. 1. 28. 17:43

> https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 이 세가지 규칙을 만족시키기 위해서는 이어진 3개의 계단 중 2개를 택해야 한다. 그보다 적게 선택할 수도 있지만, 굳이 최대값을 구함에..

C++/Baekjoon 2024. 1. 28. 16:41

> https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 이 문제도 Dynamic Programming으로 해결할 수 있습니다. 가장 큰 경로를 선택한다는 것은 결국 꼭대기에서 얻을 수 있는 최대가 되는 경우를 찾는 것이다. 결국 아래부터 자신의 위치에서 최대값을 구해 올라온다면 꼭대기에서도 최대가 되는 값을 구할 수 있다. 이런식으로 > #include using namespace std; int sum[500][500]; int main() { int num; cin >> num; for (int i = 0; i < ..

C++/Baekjoon 2024. 1. 28. 15:03

> https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 사실 DP를 이용하는 문제라는 것을 알고 풀기 시작해서 어떻게 사용할 수 있을지부터 고민했습니다. 풀이방법은 뒤에서 부터 최소값을 구해오는 방식입니다. 맨 뒤부터 각 자리를 기준으로 최솟값을 찾아갑니다. 47 25 29는 뒷 줄에서 자신이 선택할 수 있는 색 중 최소값을 찾아 가져옵니다. 그러면 66 44 89가 되고, 65 13 15는 이 중 자신이 고를 수 있는 최소값..

C++/Baekjoon 2024. 1. 28. 02:54

> https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2차원 테이블로 각 조합들을 다 채워넣고 최대값을 찾으려니 당연히 시간초과가 뜨는 것을.... 풀이 방법은 이렇습니다. 0~num 배열에 0번 부터 각 연속합을 저장하는데, ( 연속합 + i번째 값 , i번째 값 ) 이 중 더 큰 값을 저장합니다. i번째 값보다 작아지면 연속합을 깨고 차라리 i번째부터 새로 시작하는 편이 좋기 때문입니다. 그러려면 연속합이 음수여야겠네요. > #include using ..

C++/Baekjoon 2024. 1. 28. 01:44

> https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 점화식 조건 찾기가 나름 수월합니다. P(i) = P(i-2) + P(i-3) 으로 Dynamic Programming을 이용해서 풀면 됩니다. > #include using namespace std; void fillTable(long long*& arr){ arr[1] = 1; arr[2] = 1; arr[3] = 1; for (int i = 4; i < 101; i++) { arr[i] = a..

C++/Baekjoon 2024. 1. 27. 23:33

> https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 조합해서 만들어낼 수 있는 경우의 수를 알아내는 문제입니다. 사실 모든 경우의 수라서 백트래킹으로 생각할 수도 있지만 Dynamic Programming으로 해결해야 하는 문제입니다. 그런데 사실 피보나치 수열이라 굳이 DP로 하지 않아도 해결할 수 있습니다. 피보나치 수열인 것만 깨닫게 되면 크게 어렵지는 않았네요. > #include using namespace std; int ma..

C++/Baekjoon 2024. 1. 27. 22:54