CPP-Shooter's Life

2048 게임을 직접 시뮬레이션 해보는 문제다.기본적인 게임 규칙을 이해하고 짜는 것이 중요하다. 최대 5번 이동시켰을 때 남는 블록들 중 최대 값을 구하는 것이라매 이동마다 상하좌우 4방향에 대해 재귀 호출로 게임판을 갱신시켜준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125..

이 문제도 다이나믹(DP) 문제이다. 제일 먼저 생각한 것은그림들을 높이 순으로 오름차순 정렬시키는 것이다. 판매가능 그림의 조건이 부분적으로 S이상만큼만 보이면 되기에최대한 그림의 높이가 낮은것부터 높은 순으로 배치하면 판매가능 그림의 갯수가 많아질 것이기 때문이다. 이를 기본 전제로 깔고 가면서각 그림의 높이와 가격을 비교하며 최대합을 구해야 한다.캐싱할 DP 배열의 값은 각 그림이 배치될 때 구할 수 있는 가격의 최대합이다. 그리고 각 그림별로 순회하면서 이전 그림들과의 높이 차를 비교하면서가격의 합을 비교, 저장하면 되겠다 생각했는데....처음부터 잘 풀려고 하면 힘드니 일단 쉽게 풀 수 있으나 무식하게 시간초과 나는 코드를 짜보았다. 1234567891011121314151617181920212..

주어진 문제에서 N과 K가 작을 때의 경우의 수를 각각 체크해보자.0~N까지의 정수 K개를 더해 합이 N이 되는 경우의 수를 구해본다. 순서는 각 N에 대해 K가 증가하는 순서이다. 그런데, 이전 값과의 차이를 잘 보면... N (합) K (정수 갯수) 경우의 수 이전 값과의 차이 (K=1일 때부터 체크) 1 1 1 (1 자신) 0 1 2 2 (0+1, 1+0) 1 1 3 3 (0+0+1, 0+1+0, 1+0+0) 1 1 4 4 (0+0+0+1, 0+0+1+0 ......, 1+0+0+0) 1 ...... ...... 2 1 1 (2 자신) 0 2 2 3 (02, 20, 11) 2 2 3 6 (002, 020, 200, 110, 011, 101) 3 2 4 10 (0002, 0020, 0200, ......