본문 바로가기
728x90

알고리즘316

[python] 백준 2195 문자열 복사 https://www.acmicpc.net/problem/2195 2195번: 문자열 복사 첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 www.acmicpc.net 문제 해결 S에서 P로 가는 경우의 수를 찾는 것보다 P에서 S로 가는 경우를 찾는 것이 더 편하다. (문자열 하나의 기본 전략인 듯) 그러면 P에서 일부분이 S의 안에 있으면 +1을 해주면 될 것이다. 대신 최대한 문자열 길이를 길게 끊어야 한다. 문자열이 S안에 포함이 안될 때 까지 계속 이어 붙인다. 포함이 안되면 거기서 끊고 ans을 +1 해주고 인덱스는 다시 거.. 2023. 4. 6.
[python] 백준 8980 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 문제 해결 택배를 옮길 수 있는 최대 개수를 구하는 문제 어떤 택배가 더 가중치 있고 하지 않으므로 그냥 많이 옮기면 된다. 그러면 가까운 거리를 많이 이용하면 좋다. 도착지점이 가까운 지점부터 나열하여 최대한 많이 담아서 가는 것이 좋다. ( ex: (0,3) 20개 (2,5) 40개 있다 했을 때 (0,3) 20개 + (2,5) 20개를 옮기는 것이랑 (2,5) 40개를 옮.. 2023. 4. 6.
[python] 백준 1781 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제 해결 데드라인을 생각하면서 컵라면 수가 큰 것을 스택 안에 넣는 문제 스택 안의 원소의 개수를 데드라인이라고 생각하면 된다. 그러면 스택 안에 원소를 데드라인이 빠른 것부터 처리를 하며 만약 컵라면은 많이가져갈 수 있는데 데드라인이 걸리면 그 전에 작은 컵라면수를 빼고 넣으면 된다. CODE import heapq n = int(input()) table = [] for _ in range(n): d.. 2023. 4. 5.
[python] 백준 16234 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 인구 이동이 진행될 때마다 계속 반복해서 진행하므로 시뮬레이션을 생각할 수 있다. 인구 이동 지역을 저장해야하므로 bfs를 이용해서 인구 이동 지역을 저장한후 평균을 그 지역 값에 넣어서 인구이동을 시킬 수 있다. 인구이동이 없으면 멈춰야한다. 이 부분에서 고민을 많이 했는데 이동한 지역이 없으면 인구 이동을 멈추는 변수 flag를 사용하여 인구 이동이 있으면 flag=1.. 2023. 4. 5.
728x90