문제 설명당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다...

오랜만에 다시 프로그래밍을 시작해보았다.문제 설명 당신은 동영상 재생기를 만들고 있습니다. 당신의 동영상 재생기는 10초 전으로 이동, 10초 후로 이동, 오프닝 건너뛰기 3가지 기능을 지원합니다. 각 기능이 수행하는 작업은 다음과 같습니다.10초 전으로 이동: 사용자가 "prev" 명령을 입력할 경우 동영상의 재생 위치를 현재 위치에서 10초 전으로 이동합니다. 현재 위치가 10초 미만인 경우 영상의 처음 위치로 이동합니다. 영상의 처음 위치는 0분 0초입니다.10초 후로 이동: 사용자가 "next" 명령을 입력할 경우 동영상의 재생 위치를 현재 위치에서 10초 후로 이동합니다. 동영상의 남은 시간이 10초 미만일 경우 영상의 마지막 위치로 이동합니다. 영상의 마지막 위치는 동영상의 길이와 같습니다.오..

다이나믹 프로그래밍 문제이다.       처음 생각했던 접근방식(오답) 간단한 DP문제일 것이라고 생각하고 익숙한 방식대로 생각했었다.예를 들어서 11은 3^2 + 1^2 + 1^2, 즉 3이 최소 항의 개수이고 1^2 + 1^2은 2의 최소 항의 개수인 2다.13은 3^2 + 2^2 + 2^2, 즉 3이 최소 항의 개수이고 2^2 + 2^2은 4의 최소 항의 개수인 2이다. 따라서 11에 가장 가까운 제곱수를 찾은 후 (FindMinSquare), -> 항 1개구하려는 N에서 그 제곱수를 빼고 나머지는 memoization을 활용하면 된다고 생각했었다. -> dp[i-pow(minSquare,2)] 그리디 + DP 방식이였는데 이 방식은 틀렸다. 최대 제곱수를 선택하는 방식이 항상 최적의 해를 보장하지..

다이나믹 프로그래밍 문제이다.         합당한 접근방식 이 문제도 처음 봤을 때 식을 어떻게 써야할지 난감했다.후회되는 점은 N=3인 케이스부터 적어서 패턴을 찾는데 시간이 오래걸렸다.오히려 N=1, N=2, N=3.. 차근차근히 케이스를 써내려갔다면 풀이에 근접했을 수도 있었다.. 1. N=1 이라면1, 2, 3, 4, 5, 6, 7, 8 ,9 가 가능하다. 2. N=2 라면10, 21, 32, 12, 43, 23, 54, 34, 65, 45, 76, 56, 87, 67, 98, 78, 89.....옆 자리수와 1이 차이나야 한다. 여기서 섬세하게 바라보면,- 마지막 수가 0이면 왼쪽에 있는 수는 무조건 1 - 마지막 수가 9라면 왼쪽에 있는 수는 무조건 8 이어야 한다. (물론 두자리 수에서는 ..

다이나믹 프로그래밍 문제이다.       처음 생각했던 접근 방식 오랜만에 DP 문제를 시도해봤는데 역시 어김없이 "어떻게 점화식을 세워야 하지?"라는 의문이 생겼다.DP 시도할 때마다 드는 익숙한 고민이다. 그나마 어느정도 풀어본 경험이 있어서dp[i] = "i번째까지 선택했을 때 최대 포도주의 양" 이라고 방향을 잡았다. 여기서 해결해야 하는건 "연속된 3잔은 마실 수 없다"  였고, 이 것을 어떻게 풀어야 할지 어려웠다.고정관념이 있었던 것이, dp[i]를 "i번째까지 선택"했다는 것을 가정했기 때문에 더 안풀렸던 것 같다.       합당한 접근방식 DP 문제 풀 때는 항상 기억하자. "각 단계에서 가능한 선택지를 모두 나열하는 방식이 도움이 된다." 어떻게 깔끔하게 식을 세울 수 있을까를 먼저 ..

합당한 접근 방식 골렘의 위치가 특정 조건에 따라서 배치되기 때문에 2차원 맵 시뮬레이션 문제이며정령이 길을 찾아서 최대한 밑으로 내려가야하므로 탐색(BFS) 문제인 것을 깨달았다. 코린이 시절 (지금도..) 처음 이 문제를 풀었을 때는 골렘을 배치하는 것 조차 어려웠었다.그 이유는 골렘이 회전하는 방식이나, 골렘이 범위 밖을 벗어나는 것을 매우 정직하게 구현했기 때문이다.   1. 골렘이 맵을 벗어나지 않게끔 구현하는 방법:- 맵의 크기가 R*C라고 해서 R*C만 할당할 필요가 없다.- R*C 범위 밖을 넘어가는 것을 막기위해 일일이 범위 체크하기보단 바깥을 1로 설정하고, 안을 0으로 설정했다.- 골렘이 맵에 들어오지 못하고 상단에 걸치는 경우를 대비해 3칸의 여분을 더 설정했다.- 따라서 골렘은 0..