개선 가능

백준 / python / 1562. 계단 수

https://www.acmicpc.net/problem/1562 문제 요약 길이가 N이고 0~9 이 모두 나오는 수 중에 인접한 숫자의 차이가 1인 수의 가짓수를 구하라. 주의사항 절대로 나올 수 없는 bitmask 가 있다. 예를 들면 1010101010. 하지만 이를 피하기 위해 dictionary 를 사용하면 더 느려진다. 이 풀이는 약 700ms 의 시간이 걸리는데 최고 30ms 대의 시간이 걸리도록 짤 수 있는 것 같다. 대칭성을 사용하여 풀이하는 것 같은데 추후 더 연구해보자. 풀이 요약 이전 상태의 마지막 숫자에서 1차이나는 수를 붙이고, 이전 상태의 경우의 수를 다음 상태의 경우에수에 더하면 된다. dp 2개를 사용하여 직전 상태와 현재 상태만을 가지고 있도록 만들었다. 이를 실행하며 b..

백준 / Python / 1509. 팰린드롬 분할

https://www.acmicpc.net/problem/1509 문제 요약 주어진 문자열을 팰린드롬으로 나눌때 나누어진 팰린드롬 갯수의 최솟값을 구하라 풀이 요약 각 팰린드롬의 시작점과 끝점을 일단 구해야한다. dp 를 사용하여 특정 idx 에서 팰린드롬을 적용시킨게 나은지, 빼는게 나은지 dp 에 기록한다. 마지막 dp 값을 출력한다. 더 나은 방법으로는 팰린드롬을 구하자마자 dp 를 갱신하는 것이다. 이렇게 하면 겹치는 로직이 생겨서 더 빨리 풀 수 있다. 아래는 팰린드롬 구하기와 dp 갱신을 나눈 로직이다. from sys import stdin from collections import defaultdict, deque input = stdin.readline _MAX = 2500 ipt = i..

백준 / python / 1208. 부분수열의 합 2

https://www.acmicpc.net/problem/1208 문제 요약 숫자 A 와 수열이 주어졌을 때 부분 수열의 합이 A 가 되는 경우의 수를 구하라. 수열의 길이는 40 이하이며 각 입력의 절댓값은 십만 이하, A 의 절댓값은 백만 이하 이다. 풀이 요약 크게 dp 와 meet in the middle 2가지의 풀이가 가능하다. DP 풀이 C($=20*10^5$) 는 center 의 약자, S 는 원하는 합이다. dp[합] = 경우의수 인 배열 dp[$40*10^5$] 을 선언한다. 입력값 A 가 들어오면 dp[A+C] 에 1을 추가한다. 0으로 초기화된 배열 new_dp[$40*10^5$] 를 준비한다. dp를 순회하면서 new_dp[idx + A] 에 dp[idx]를 더하고 new_dp[i..