건물에 완전히 전파되기까지 시간이 걸려서 굉장히 까다로운 문제였다.건물이 완전히 전파되기까지는 방문처리를 하면 안되고, 완전히 전파되면 인접 구역으로 전파된다는 점이 고민을 많이 하게했던 문제같다.풀이 고민처음에는 큐에 (전파까지 남은 시간, y좌표, x좌표)의 형태로 관리하려고 했다. 만약 건물이라면 Tb의 시간을 넣고 이후 큐에서 빼고 1씩 감소시킨 뒤 다시 넣어줬고, 건물이 아니라면 0의 시간을 넣었다. 그래서 남은 시간이 0인 경우에만 인접 좌표로 전파시키도록 했는데, 아마 넣었다 빼는 과정에서 시간 초과가 난 것 같다. 그 뒤에는 방문 처리를 3차원 배열을 통해서 수행해보려고 했다. 건물이 Tb의 시간 이후에는 모든 층에 퍼지게 되므로 Tb의 층을 가진다고 볼 수 있다.이렇게 v[Tb][y좌표]..
python
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]로 작성해서 틀리는 일이 잦았다. 비교의 목적을 제대로 상기할 필요가 있다. 만약 내가 헷갈렸던 코드 그대로 사용하게 되면 현재 선택된 물건을 가방에 넣는 것과 넣지 않는 것을 비교하는 것이기 때문에 무조건 물건을 넣는 쪽이 가치가 더 높다. 하지만, 현재 선..
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..
