추측보다는 측정

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

문제:www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 처음에 이 문제를 접 했을 때 기존 더하기 문제와 같이 피보나치의 꼴처럼 이전의 값을 단순히 더해나가면 될 줄 알았다. 그래서 문제의 푸는 방향을 오로지 총 갯수의 상관관계만 봤는데 그렇게 접근하면 안됐다. 이 문제는 사실 RGB거리 문제와 유사한 문제라 볼 수 있다. 방향성을 한 번 잘 못 잡으니깐 다른 방법이 생각이 나질 않았다. ㅠㅠ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 MAX = 100000 mod =..

문제: www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 이 문제는 이해를 못한 것이 컸다. 문제 자체는 오등수 문제와 비슷하다는 것은 인지하고 있었는데 문제에 대하여 제대로 이해를 못해서 결국 블로그를 참조하게 되었다. 원리 자체는 오등수와 비슷하다. 오등큰수는 이제 비교 대상이 자신의 값 자체가 아닌 그 값의 갯수라는 것에 대한 차이점이 있을 뿐이다. 결과를 저장할 리스트와 스택 그리고 각 숫자에 대한 갯수를 저장하는 배열이 필요하다. 갯수는 사전형식을 이용하여 갯수를..

문제:www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 이 문제에서 막힌 부분은 시간초과 였다. 쇠막대기 문제와 비슷한 이유였다. 최악의 경우 시간복잡도 문제가 N^2이 나오기 때문이다. 아래의 코드는 시간초과로 틀렸던 코드이다. 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 39 40 41 #include #include #inclu..

문제:www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 처음에 문제를 풀 때 '()'를 'l'로 치환을 한 다음에 두개의 리스트를 만들고 하나의 리스트에는 ')'를 만나기 전까지의 문자를 저장하였고 나머지 리스트는 ')'를 만났을 때 '('를 만나기 전까지의 'l'의 갯수를 센 다음에 저장을 하고 초기화하는 방식으로 풀었다. 그런데 그 결과는 '시간 초과'라는 결과를 가져왔다. 그렇게 된 이유는 최악의 경우에 시간 복잡도가 N^2이기 때문이다. 1 2 3 4 5 6 7 ..