추측보다는 측정

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

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