건물에 완전히 전파되기까지 시간이 걸려서 굉장히 까다로운 문제였다.건물이 완전히 전파되기까지는 방문처리를 하면 안되고, 완전히 전파되면 인접 구역으로 전파된다는 점이 고민을 많이 하게했던 문제같다.풀이 고민처음에는 큐에 (전파까지 남은 시간, y좌표, x좌표)의 형태로 관리하려고 했다. 만약 건물이라면 Tb의 시간을 넣고 이후 큐에서 빼고 1씩 감소시킨 뒤 다시 넣어줬고, 건물이 아니라면 0의 시간을 넣었다. 그래서 남은 시간이 0인 경우에만 인접 좌표로 전파시키도록 했는데, 아마 넣었다 빼는 과정에서 시간 초과가 난 것 같다. 그 뒤에는 방문 처리를 3차원 배열을 통해서 수행해보려고 했다. 건물이 Tb의 시간 이후에는 모든 층에 퍼지게 되므로 Tb의 층을 가진다고 볼 수 있다.이렇게 v[Tb][y좌표]..
전체 글
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번] 파이썬 - 불끄기 풀이 현재 줄의 상태에 따라 바로 아랫줄의 점등 여..