추측보다는 측정

문제:www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 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 import sys N,S=map(int,sys.stdin.readline().rstrip().split()) li = ..

문제: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=[..

문제:www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이 문제를 처음에 봤을 때 lower_bound 와 upper_bound의 관계를 이용하면 되지 않을까 하고 이에 대하여 코딩을 짰었는데 100과 가까운 숫자에 대하여 어떻게 처리해야 할지 감이 안왔다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import sys def solve(sub): global ans for p i..