21년 10월 2주차 PS 일지

CP는 안한지 꽤 됐지만, PS는 꾸준히 하고 있는데 이렇게 포스팅이 늦은 이유는.... 게을러서입니다ㅋㅋㅋ

 

백준 10160 암호

 

dp(i) : 1~i까지 처리 했을때, 가능한 안전한 암호의 갯수

위와 같이 디피 배열을 정의합니다

 

그렇다면 다음과 같은 점화식을 도출 할 수 있습니다

$dp_{i} = K*dp_{i-1} - 2*dp_{i-5} + dp_{i-7}$

 

i까지 가능한 암호의 갯수는 i-1개까지의 가능한 갯수에 K를 곱해준 경우에서 뒤의 5글자가 안전하지 않은 패턴인 경우를 빼주면 구할 수 있습니다

다만 여기서 디피에서 관리하는 값은 안전한 암호의 갯수라는 점에서 AB/ABCBC 이런 경우는 없기 때문에 다시 dp(i-7)을 더해주어야 합니다(AB/ABCBC 이런 패턴은 안전한 암호만을 저장하기 때문에 배열에 존재하지 않기 때문입니다)

그러니까 우리는 지금 모든 문자 패턴에서 뒤에가 ABCBC인 갯수를 빼주었는데 이렇게 빼준 경우의 수 안에는 AB/ABCBC 이런 패턴도 포함되기 때문에 1*1*dp(i-7)를 빼주어야 합니다

 

백준 14956 philosopher's walk

 

구사과님 블로그에 아주 좋은 풀이가 있습니다

아무튼 저도 정확히 같은 방식으로 풀이했습니다

재귀적으로 생각해서 문제를 풀어주면 되는데 이때 우하단 처리가 상당히 까다롭습니다

auto res = sol(K-1, step%tmp2);
res = {2*tmp-res.second+1, tmp-res.first+1};

위와 같이 우하단 처리를 하면 쉽게 해결 할 수 있습니다

 

백준 3020 개똥벌레

 

F(i): 높이가 i일때 부셔야하는 석순의 갯수
T(i): 높이가 i일때 부셔야하는 종유석의 갯수
S(i) = F(i)+T(i)
ans = min(S(k)), 1<= k <= H

 

이때 두 함수 F,T를 선형시간 안에 구해주어야 합니다
이는 아래와 같은 방법으로 해결 할 수 있습니다
H(i): i번째 석순/종유석의 높이일때,
H(i)=k이면 배열의 첫번재 원소에 1을 더해주고 k+1번재 원소에 -1을 더해줍니다
이렇게 구한 배열을 이용해 누적합을 구해주면 문제를 해결 할 수 있습니다
이때 배열의 i번재 원소에는 높이가 i일때 부셔야하는 석순/종유석의 갯수가 들어있다는 것은 조금만 생각해 보면 알 수 있기 때문에 설명은 생략ㅋㅋ