추측보다는 측정

문제:www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이 문제는 처음에 문제 자체를 이해 못한 것이 컸다. 문제를 이해해도 어떻게 풀어야 할 지 막막해서 결국 다른 분들의 코드를 참조했다. from collections import deque import sys input = sys.stdin.readline k = int(input()) def bfs(start): bi[start] = 1 q = deque() q.append(start) wh..

문제:www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 이 문제는 비트마스크의 개념을 정확히 몰랐을 때라 그런지 감이 전혀 안왔다. 처음에는 그냥 우선 자릿수가 큰 게 더 크므로 가로로 싹 다 더한 값과 세로로 싹 다 더한 값 중 큰 거 아닐까 하는 생각을 했지만 역시 예외는 있었다. def bitmask(): global maxAns # 비트마스크로 2^(N*M)의 경우의 수를 따져본다 for i in range(1

문제:www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net import sys N=int(sys.stdin.readline()) ar=[] passing=[False]*(N) for _ in range(N): ar.append(list(map(int,sys.stdin.readline().split()))) li = [int(i) for i in range(N)] ret=10e9 def func(ans,celi,aim):..

문제:www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net 이 문제를 처음 접근했을 때 우선 N번째까지 해당하는 수열을 구하고 나머지의 수열을 확인하는 식의 코드를 작성했었다. 하지만 그것의 큰 문제점은 시간초과 문제였다. 시간초과 문제를 결국 해결하지 못해서 다른 분들의 코드를 참고하였다. def ck(idx): hap = 0 for i in range(idx, -1, -1): hap += result[i] if hap == 0 and S[i][id..

문제:www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net import sys N = int(sys.stdin.readline().rstrip()) li=[] for _ in range(N): li.append(list(map(int,sys.stdin.readline().rstrip().split()))) travel=[False]*N final=0 ret=10000000000 def func(y,x,final,ans,..

문제:www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는 N과M에서 했던 것을 이용하여 풀면 시간초과나는 것이 확정이기 때문에 그 방법으로 안 풀었다. 그렇다고 어떻게 풀어야 할 지 몰라서 결국 다른 분들이 어떻게 풀었나 찾아보았다. 풀이법은 이 블로그를 통해 봤다. 참고: fieldanimal.tistory.com/24 백준 10972 다음 순열 https://www.acmicpc.net/problem/10972 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

문제:www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import sys N,M = map(int,sys.stdin.readline().split()) li=[int(i) for i in sys.stdin.readline().split()] check=[0]*10001 passing=[..

문제: www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import sys N,M = map(int,sys.stdin.readline().split()) li=[int(i) for i in sys.stdin.readline().split()] check=[0]*10001 passing=[..