본문 바로가기
728x90

전체 글423

[python] 백준 17070 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 해결 파이프는 그래프에서 0좌표에만 놓을 수 있다. (1은 벽이므로) 파이프를 놓는 방법의 수는 이전 장소 (r,c) 좌표면 (r-1,c), (r,c-1), (r-1,c-1) 좌표의 영향을 받는다. 각 좌표에 어떻게 놓느냐에 따라 경우의 수가 달라진다. 문제의 그림을 참고하는 것이 좋다. DP를 3차원을 이용해서 풀면 충분히 쉽게 풀 수 있다. CODE n = int.. 2023. 3. 9.
[python] 백준 2096 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 해결 사실 문제 자체는 매우 쉽다. (dp를 이용해서 0열, 1열, 2열에 각각 올 수 있는 이전 행 최고 누적합을 가져오서 더하면 되므로) 하지만 메모리가 4MB 밖에 안주어진다. 정확한 양은 체감을 못해도 평소 250~500MB 되는 문제도 많은 것을 보면 엄청 적다는 것을 알 수 있다. 따라서 리스트를 n행 모두 사용하는 것이 아니라(dp[0], dp[1], .... 사용하면 메모리가 커진다..) 한.. 2023. 3. 7.
[python] 백준 14503 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 해결 한칸씩 정해진 규칙대로 움직이면서 청소 안된 곳 청소하는 것으로 구현하는 문제 사실 어렵진 않지만 처음 원본 그대로 deepcopy를 해야한다. 그 이유는 처음 0, 1은 단순히 청소 안된 곳, 청소 된 곳을 의미하는 것이 아니라 이동할 수 있는 곳, 이동 할 수 없는 곳(벽)을 의미하는 것이기도 하기 때문이다. 따라서 아래 코드는 vi.. 2023. 3. 7.
[python] 백준 14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 벽을 어떻게 세워야하는가? → 상황에 따라 다르다. So 모든 경우 다 해봐야 한다. 재귀 사용! 최대 영역을 어떻게 구하는가? 전염 되는 지역을 계속 이동 시킨 후 더이상 전염이 안될 때 전염이 안된 일반 지역의 구역 개수를 구하면 된다. 전염지역 구하기 위해 bfs() 할 때 계속 graph 값이 바뀌므로 copy.deepcopy를 이용해 복사본으로 돌리는 것이 좋다! copy 라이브러리 알아두.. 2023. 3. 6.
728x90