[백준 / C++] 5557번: 1학년 (다이나믹 프로그래밍, dp)

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 난이도: solve.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 및 구현 i - 1 번째 수까지 사이에 + 또는 - 집어넣어 계산한 결과가 j이고, 이를 만드는 경우의 수가 n개라고 해보자. 나는 이걸 이렇게 표현했다. dp[i - 1][j] = n i 번째 수(arr[i])가 x라고 하자. 그럼 위의 경우에서 i 번째 수까지 계산한 결과는 j - x 또는 j + x..

• format_list_bulleted PS/백준
• · 2023. 9. 15.
• textsms

[백준 / C++] 11052번: 카드 구매하기 (dp)

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 및 구현 1개의 카드부터 시작해 N개의 카드까지 차례로 구매하는 데 필요한 최대 금액을 계산한다. 계산한 값은 배열 P에 저장했다. 최대 금액을 계산하는 방법은 간단하다. i개의 카드를 살 때 최대 금액을 계산한다고 해보자. 이때 1개부터 i - 1개의 카드를 살 때의 최대 금액은 이미 알고 있다고 하자. i개의 카..

• format_list_bulleted PS/백준
• · 2023. 8. 4.
• textsms

[백준 / C++] 2565번: 전깃줄 (LIS 응용)

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍, LIS 접근 방법 전깃줄이 겹치지 않으려면 A 전봇대에서 이어지는 B 전봇대의 번호가 오름차순이어야 한다. 따라서 자르는 전깃줄의 개수를 최소화하려면 LIS를 찾아야 한다. 가장 긴 증가하는 부분 수열만을 남기고 나머지는 다 잘라버려야 한다. 구현 LIS 알고리즘 사용해서 (11053번 포스팅 코드 참고) 가장 긴 수열의 길이를 구하..

• format_list_bulleted PS/백준
• · 2023. 7. 31.
• textsms

[백준 / C++] 11054번: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 11053번을 풀었다면 아주 쉽게 풀 수 있는 문제다. https://jangkunstory.tistory.com/37 [백준] 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를..

• format_list_bulleted PS/백준
• · 2023. 7. 28.
• textsms

[백준 / C++] 14002번: 가장 긴 증가하는 부분 수열 4 (dp)

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 일반적인 dp를 이용한 N^2짜리 LIS 풀이로 가장 긴 부분 수열의 길이를 구하고 추가적인 코드를 통해 O(N)에 경로를 추적할 수 있다. 일단 LIS의 길이를 구하는 for문을 마치고 나면 len[i]에는 A[i]를 부분 수열의 마지막 원소로 썼을 때의 LIS 길이가..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms

[백준 / C++] 2193번: 이친수 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 0은 여러개 이어져도 상관없다. 1은 2개 이상 연속되면 안 된다. 따라서 0 이전의 숫자는 0 또는 1이 가능하고, 1 이전의 숫자는 0만 가능하다. 그럼 점화식은 아래와 같이 나타낼 수 있다. n번째 숫자가 0인 경우의 수: dp[n][0] = dp[n-1][0] + dp[n-1][1] n번째 ..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms