Junnnho

BOJ : https://www.acmicpc.net/problem/11052

GitHub : https://github.com/junho0956/Algorithm/blob/master/11052/11052/%EC%86%8C%EC%8A%A4.cpp

아직도 solved.ac 에 의하면 실버수준인데도 DP는 진짜 갈길이 막막하다

진짜 점화식 찾는게 너무어렵다.. 진짜 이제 이정도 수준인데 숨이 막히고 포기하고 싶어진다 ㅠ

점화식을 간단히 설명해보자면

N개중 i개를 구매하는 시점, j번째 카드를 구매하는 시점일때

dp[i] 는 i개를 구매할 때 최댓값이고

dp[i-j]는 i개 중에서 j번째 카드를 구매하지 않은 경우 최대값이 된다. card[j]는 j번째 카드의 가격이 되겠고

결국 j번째 카드를 살지 말지를 표현하여 주면 점화식이 완성된다.

dp[i] = max(dp[i], dp[i-j]+card[j]) ..

너무 어려워서 눈물날꺼같다..

BOJ : https://www.acmicpc.net/problem/2225

GitHub : https://github.com/junho0956/Algorithm/blob/master/2225/2225/%EC%86%8C%EC%8A%A4.cpp

DP 시작한지 얼마안됬지만 정말 너무 어려운것 같다..

진짜 solved.ac 에서 부여하는 랭크 기준으로 DP는 골드문제까지는 막힘없이 풀 수 있는 능력을 가지고싶다..

합분해는 규칙만 알고나니 쉬운 문제였다.

N 을 K 개로 합분해하는 경우의 수는 0~N 을 K-1 개로 합분해하는 경우의 수의 합이다.

이를 이용하여 재귀로 간단하게 풀 수 있었다.

BOJ : https://www.acmicpc.net/problem/9461

GitHub : https://github.com/junho0956/Algorithm/blob/master/9461/9461/%EC%86%8C%EC%8A%A4.cpp

시계방향으로 그려지는 파도반수열은

-2, -3번째 수열과 만난 합으로 그려진다.

BOJ : https://www.acmicpc.net/problem/2133

GitHub : https://github.com/junho0956/Algorithm/blob/master/2133/2133/%EC%86%8C%EC%8A%A4.cpp

잘 정리된 블로그가 있어 주소를 남겨봤습니다. https://mizzo-dev.tistory.com/entry/baekjoon2133

타일채우기 문제에는 특정한 규칙이 있습니다.

1. 2*1, 1*2 형식의 짝수형 타일이므로 N이 홀수가 되면 빈공간이 생겨 채울수 없는 문제가 발생합니다.

2. 짝수개(2)씩 늘어나는 타일채우기형이므로 짝수+짝수를 하게되면 중간부분에 특정모양이 새로 생기게 됩니다.

3*2 와 3*4 의 그릴 수 있는 형태만 그려보면 3*6, *8, *10,

이렇게 짝수개로 늘어날때 2개씩 특정모양이 생기게 됨을 알 수 있습니다.

3*2 를 3개로 기본값을 보고

3*4 를 채우기 위해서는 (3*2) * (3*2) + (3*4)의 고유모양 2개 = 9+2 = 11

3*6 를 채우기 위해서는 (3*2) * (3*4) + (고유모양 3*4)*(3*2) 개 + (3*6)의 고유모양 2개 = 33 + 6 + 2 = 41

3*8 를 채우기 위해서는 (3*2) * (3*6) + (고유모양 3*4)*(3*4) 개 + (고유모양 3*6) * (3*2) 개 + (3*8)의 고유모양 2개

123+25+6+2 = 153 이 됨을 알 수 있습니다.