728x90 백트래킹12 [python] 백준 15686 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해결 치킨집을 m개로 줄여서 각 집에서 치킨집까지 최소거리 합을 구해야한다. 치킨집을 m개로 줄이는 경우의 수는 combinations 라이브러리를 이용하면 좋을 것이다. 그러기 위해서는 치킨집 좌표를 알아야할 것이다. for문을 통해 치킨집 좌표와 집 좌표를 구해놓자. 치킨집 m개를 뽑은 다음 집 하나 치킨집 하나씩 매칭 시켜가며 최소거리 합을 구해본다. 시간복잡도가 .. 2023. 3. 5. [python] 백준 1182 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 ●리스트 안의 숫자가 매우 다양하고 주어지는 수열이 특징은 알 수 없으므로 모든 경우의 수를 다 계산해 봐야 할 것이다. ●부분수열의 합을 알아야 하기 때문에 부분수열의 순서는 상관이 없다. 따라서 i개(i>0)를 순서없이 뽑았을 때 합이 s가 되면 답을 +1을 해주면 된다. CODE import sys input = sys.stdin.readline.. 2023. 1. 19. [python] 백준 6603 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제 해결 combination(조합) 라이브러리만 쓸 줄 알 면 쉬운 문제 for문 반복으로 출력하면 된다. CODE from itertools import combinations import sys input = sys.stdin.readline while 1: S = list(map(int, input().split())) if S[0] == 0:break for comb in c.. 2023. 1. 12. [python] 백준 10971 외판원 순회2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제해결 dfs 는 써야된다는 생각이 바로 든다. (계속 반복적으로 판별하여 이동하므로) 마지막에 처음 시작지점으로 돌아와야 하므로 처음 시작점은 기억해두어야한다. 현재 지점(now)에서 이동할 지점(next)로 갈 때 주의할 점은 한번도 가본적이 없어야 한다는 것(단 시작점으로 마지막 이동할 때 제외)과 지금 비용이 최소비용일 가능성이 있어야 한다는 .. 2023. 1. 11. 이전 1 2 3 다음 728x90
