![]()
1938 : 통나무 옮기기 처음에 계속 메모리 초과가 났는데 다시 생각해보면 회전 로직에서 시간 초과가 났던 것 같다.회전 시 통나무의 중심축을 제외한 두 좌표에 대해 y값과 x값이 바뀐다고 생각을 했었다.. 그렇게 생각하니 아래와 같이 정렬을 해줘야 했고 불필요한 리스트를와 패킹하기 위해 또다른 리스트를 만들었다. 아마 이부분에서 시간 초과가 난게 아닌가 싶다.# 따로 정렬이 필요if can_turn(y2, x2): # 변형 n_pos = sorted([(x1, y1), (y2, x2), (x3, y3)]) n_pos = tuple([*n_pos[0], *n_pos[1], *n_pos[2]]) if n_pos in v: continue v.add(n_pos..
14728 : 벼락치기배낭문제로 풀 수 있는 문제인데 배낭문제를 풀 때마다 헷갈리는 부분이 있어 기록으로 남기려고 한다.for j in range(time, T + 1): dp[i][j] = max(dp[i - 1][j - time] + score, dp[i - 1][j])이 부분의 max(dp[i - 1][j - time] + score, dp[i- 1][j])를 매번 max(dp[i - 1][j - time] + score, dp[i][j]로 작성해서 틀리는 일이 잦았다. 비교의 목적을 제대로 상기할 필요가 있다. 만약 내가 헷갈렸던 코드 그대로 사용하게 되면 현재 선택된 물건을 가방에 넣는 것과 넣지 않는 것을 비교하는 것이기 때문에 무조건 물건을 넣는 쪽이 가치가 더 높다. 하지만, 현재 선..
![]()
14939번: 불 끄기 어제 99클럽 알고리즘 스터디에서 봤던 문제랑 유사하지만 약간 다른 점이 있다. 불가능한 경우가 존재하고 불가능할 경우 -1을 출력해야한다는 점 상태가 켜고 끄는 2가지 경우에 열이 10칸이므로 한 줄당 2^10(1024)가지의 경우의 수가 있다는 점 어제는 4방향 * 최대 8칸으로 4^8(65,536)가지의 경우의 수 어제 첫 줄부터 고정시켜 놓으며 바로 아래 줄의 회전 횟수가 정해진다는 아이디어를 듣고 나서 문제를 풀어보려고 시도했으나 이를 어떻게 구현해야할지 감이 잘 안잡혔다. 결국 다른 분들 풀이를 참조했다. [백준] 14989 - 불 끄기 💡 / 플래티넘 5 / 브루트포스 & 그리디 [백준 14939번] 파이썬 - 불끄기 풀이 현재 줄의 상태에 따라 바로 아랫줄의 점등 여..
2253 : 점프 처음에는 갈 수 있는 가지수인줄 알았는데 최소 움직임 횟수였다. 명심할 것 문제 잘 꼼꼼히 읽기 경계값 체크하기기존 코드에서는 2번째 칸을 무조건 이동가능하게 해뒀는데 2번째 칸 역시 작아서 밟지 못할 수 있다. 이 부분에서 문제가 생겨서 계속 오류가 났다. 예제와 같이 6, 11, 16번 칸을 못 밟는 경우 아래와 같다. 1번째 칸에서 한칸만 이동 가능하다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 0 1 2 3 4 5 6 7 2번째 칸에서는 1의 속도로 점프했으므로 다시 1의 속도로 점프하거나, 가속해서 2의 속도로 점프할 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 0 1..
