본문 바로가기
728x90

알고리즘316

[python] 백준 14442 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 해결 (0,0)에서 (n-1,m-1)까지 이동하는 문제 갈 수 있는 길이 있고 없는 길이 있다. 하지만 예외적으로 k번 갈 수 없는 길을 갈 수 있다. 따라서 visited[i][j]에서 예외포인트 k번 까지 가능하다는 것에서 visited[i][j][k]의 방문 여부를 확인하는 것이 편하다. visited[i][j][k]의 값은 (i,j)까지 벽을 깰 수.. 2023. 3. 14.
[python] 백준 1213 팰린드롬 만들기 https://www.acmicpc.net/problem/1213 2023. 3. 13.
[python] 백준 1965 상자넣기 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 해결 이전의 상자들이 영향을 주기 때문에 dp 이용해야 한다는 느낌이 든다. 하지만 어느 상자를 마지막에 넣어야 할 지는 잘 알 수 없다. 마지막에 넣을 수 있는 상자의 인덱스를 미리 알아본다. (for문을 통해) dp[i]를 i상자 안에 있는 최대 상자 개수라고 하면 for문을 통해 i보다 작은 인덱스 상자 중 넣을 수 있는 상자 최대 개수와 dp[i]를 비교해가며 최댓값으로 dp[i]를 수정해간다.. 2023. 3. 12.
[python] 백준 1915 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 해결 가장 큰 정사각형의 크기를 구하는 것이기 때문에 DP를 이용하는 것이 좋다. (i,j) 좌표를 끝으로 하는 가장 큰 정사각형은 (i-1,j-1) 좌표를 끝으로 하는 가장 큰 정사각형 크기에 영향을 받는다. DP를 가장 큰 정사각형의 한 변의 길이라고 하면 DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) +1 이 될 것이다. CODE import sys input = sys.stdin.readline n, m =.. 2023. 3. 12.
728x90