목록1차원 DP (2)

기록

백준_1509_팰린드롬 분할

문제 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 1) 분할된 팰린드롬의 최소 개수 문자열 ABACA가 주어졌을 때 해당 위치 안에서 찾은 팰린드롬을 아래처럼 표현할 수 있다. 각 위치에서 분할된 펠린드롬의 최소 개수를 저장하면, 문자열 전체에서 분할된 팰린드롬의 최소 개수를 저장할 수 있다. dp[e] = min(dp[s]+1, dp[e]) 팰린드롬의 최소개수를 dp로 구하는 풀이(시간초과) def isPal(s, e) : whil..
코딩테스트/python 2022. 10. 10. 20:00
프로그래머스_스티커 모으기(2)

문제 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 풀이 N개의 스티커가 원형으로 연결되어 있으므로 (1) 첫번째 스티커가 쓰이는 경우와 (2) 첫번째 스티커가 쓰이지 않는 경우로 나누어서 생각해야 한다. (1) 첫번째 스티커가 쓰이는 경우 dp에는 0번째 스티커를 사용하고 1번째 스티커를 사용하지 않은 경우 i까지의 최대 값을 저장한다. dp[i-1] : i번째 스티커를 사용하지 않음 dp..
코딩테스트/python 2021. 6. 16. 14:11
Prev 1 Next