본문 바로가기

백준28

[구현] 백준 16234 : 인구이동 - 파이썬 Python https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 생각하기 문제에서 제시된 기준을 기반으로 인구가 각 날에 이동할 수 있는 블락들을 bfs를 이용하여 묶어본다 묶을 수 있다면 계속 이동해도 된다는 얘기 -> 묶지 못할 때까지 계속 day를 증가시켜가면서 이동해보자 시간복잡도 모든 칸에 대해서 조사 : O(N^2) 최대 인구 이동 가능 : 2000 2000 x ( N^2 ) 구현하기 united - bfs를 돌면서 묶을 수 있는 박스.. 2022. 1. 31.
[DP] 백준 11066번 : 파일 합치기 - Python 파이썬 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 생각하기 파일을 합치는데 연속된 파일들을 합치는 것이 포인트였다 1 2 3 4 의 파일들이 있다면 1 (2,3,4) (1, 2) (3, 4) 1, 2, 3) 4 -> 3가지의 경우 중에서 작은 합치는 비용을 찾으면 된다 결국 작은 문제들이 합쳐져서 큰 문제의 답을 이루는 DP를 사용하면 된다는 것을 알았다 점화식을 세워보면 dp[i][j] 는 i번째 data 부터 j번째 data까지 합치.. 2022. 1. 21.
[DP] 백준 15989번 : 1,2,3 더하기 4 - 파이썬 Python https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net n을 1,2,3의 합으로 나타내는 개수는 이전 수를 1,2,3의 합으로 나타냈을 때의 수에 영향을 받는다 dp방법으로 풀어내기로 한다 중복되는 1 2 1 / 1 1 2 같은 조합을 없애기 카운팅 안하기 위해서는 각각의 조합에서 대표만 카운팅해야 함 1 1 2 같은 경우만 카운팅 하기 위해서는 1을 사용하는 방법과 2를 사용하는 방법을 .. 2022. 1. 16.
[DP] 백준 11060번 : 점프 점프 - Python 파이썬 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 생각하기 어디로 가는가? 무조건 오른쪽으로 점프하므로 문제의 크기가 점점 작아진다 마지막 칸에 오는 방법은 모두 이전들 칸에서의 방법중 하나이다 dp[i] : 각 칸 도착시의 최소 점프 횟수 이렇게 설정해놓으면 마지막 칸까지 각칸을 경유해서 점프해 나갈때, 모두 최소인 칸만 경유하는 것이므로 마지막 칸도 최소가 된다 구현하기 0번째 칸부터 시작해서 N-1번째 칸까지 N-1을 넘지 않는 .. 2022. 1. 12.

티스토리툴바