추측보다는 측정

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

문제:www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net import sys n = int(input()) m = [] for _ in range(n): m.append([int(i) for i in sys.stdin.readline().split()]) ret = 1001*1001 for x in range(3): dp = [[0 for _ in range(n)] for _ in range(3)] for i in range(3): ..

문제:www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 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 36 37 38 import sys def gcd(left,right): if right==0: return left return gcd(right,left%right) testCase = in..

문제:www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 1,2,3더하기 5 에서 경험했던 것을 토대로 풀었다. 맞긴 맞았는데 시간에 대한 개선이 필요한 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import sys N=int(sys.stdin.readline().rstrip()) loc=0 mod=1000000009 li=[] for _ in range(N): li.append(int(sys.stdin.readline().rstrip())) loc=ma..

문제:www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 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 import sys N = int(sys.stdin.readline().rstrip()) quest = [0]+list(map(..

문제:www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제의 경우 dp를 팩토리얼 개념으로 접근하다가 틀린 케이스다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import sys N,K= map(int,sys.stdin.readline().rstrip().split()) dp = [-1]*202 div=1000000000 dp[0]=1 dp[1]=1 def factorial(n): if n==1 or n==0: return 1 if dp[n]!=-1: return dp[n] dp[n]=(n*factorial(n-1)) return (n*fac..

문제:www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 이 문제는 c++로 제출했을 때는 통과했는데 python3로 제출했을 때는 시간초과가 난 문제이다. 또 이상하게 pypy3로 제출했을 때는 통과했다. 풀이법은 이제 제곱형태는 1로 저장하고 그 외의 다른 것은 1부터 루트값까지 반복문을 통하여 최소값을 찾은 다음에 저장하는 방식으로 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys..