728x90 브루트포스23 [python] 백준 15661 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 해결 팀을 정하는 것부터 하나 하나 다 해봐야 하기 때문에 상당히 시간복잡도가 클 것 같다.(팀원 수도 양수라는 것 외에 정해지지 않음) 결국 팀원 하나하나 정하는 것을 재귀를 통해서 정리하고 계산을 하여 최솟값을 구한다. 파이썬으로는 시간초과가 나와서 pyp3로 풀었다. CODE import sys input = sys.stdin.readline.. 2023. 1. 16. [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. [python] 백준 14500 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 사실 너무 어려웠다. 한 점을 잡고 이동을 해야할 것 같은데 어떻게 해야할 지 몰랐다. 이 모양을 제외 하면 모두 한 붓 그리기, 즉 다시 되돌아가지 않고 이동하면서 그릴 수 있다는 특징이 있다. 이 모형도 가운데를 중심으로 동,서,남,북 으로 이동 후 하나를 자른다는 생각을 할 수 있다. 자르는 것은 최소의 값을 가진 지역이라 할 수 있다. 이동하는 방법을 move = [ (1,0),.. 2023. 1. 2. 이전 1 ··· 3 4 5 6 다음 728x90
