DP14 [백준] 21549 - Московские числа (c++) Russian Olympiad in Informatics > Russian Olympiad in Informatics 2021 5번 문제이다.https://www.acmicpc.net/problem/21549 문제 요약로마 숫자와 비슷한 모스크바 숫자를 만들려고 한다. 모스크바 숫자의 각 자릿수는 알파벳으로 이루어져 있고 각 자릿수에 해당하는 값은 다음과 같다. 숫자의 값은 각 자릿수 기여값의 합이다. 각 자릿수의 기여값은 오른쪽에 더 큰 값이 없으면 (+자릿수값)이고 있으면 (-자릿수값)이다. 테스트케이스 마다 대문자 알파벳과 ?가 조합된 문자열이 주어질 때 ?자리의 올 알파벳을 결정하여 최대값을 만들고 숫자의 값과 완성된 문자열을 출력해라. *문자열의 총 길이는 300,000을 넘지 않는다. 풀이 (.. 2024. 8. 28. [백준] 15747 - Taming the Herd (c++) USACO 2018 February Contest > Gold 3번 문제이다.https://www.acmicpc.net/problem/15747 문제 요약N길이의 수열 a가 주어진다.수열을 k개의 그룹으로 나눌 수 있는데 각 그룹은 0부터 1씩 증가하는 수열이 된다.수열을 1~N개로 그룹으로 나눴을 때 a와 다른 원소 개수의 최솟값을 각각 구해라. 풀이 (N^3)DP문제 이해만 했다면 DP 문제란 걸 쉽게 알 수 있다. 갱신하는 게 조금 어려웠는데 이렇게 할 수 있다.일단 dp[i][j]를 i까지 j개의 그룹으로 나눴을 때 다른 원소 개수의 최솟값으로 정의하고 dp[i][j]에서 dp[i+1~n][j+1]의 최솟값을 갱신해 나가면 된다. 이렇게 하면 N^3의 시간복잡도로 dp테이블을 전부 채울 수 있다.. 2024. 8. 21. 이전 1 2 3 다음
