[백준 2747] 피보나치 수 (C++)
https://www.acmicpc.net/problem/2747 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.입력 첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 수를 출력한다. 문제 풀이dp 기초 문제.dp 배열을 선언하여 d..
2024. 7. 24.
[백준 11048] 이동하기 (C++)
https://www.acmicpc.net/problem/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)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오. 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)둘..
2024. 7. 20.
[백준 17216] 가장 큰 감소 부분 수열 (C++)
https://www.acmicpc.net/problem/17216문제수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 이고, 합은 186이다. 입력 첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다.(1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다. 문제 풀이LIS 알고리즘.일반적인 LIS 알고리즘에서는 dp 배열에 증가하는 형태이..
2024. 7. 16.
[백준 5557] 1학년 (C++)
https://www.acmicpc.net/problem/5557문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수..
2024. 6. 21.