코딩테스트

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 코드 My answer a=[0,1,2,4]+[0]*8 n=int(input()) for i in range(4,12): a[i]=a[i-1]+a[i-2]+a[i-3] for i in range(n): tmp=int(input()) print(a[tmp]) Another answer dp=[1,2,4] for i in range(4,12): dp.append(sum(dp[-3:])) for _ in range(int(input())): print(dp[int(input())-1]) 풀이 우선 맨 처음에 문제를 잘못 이해해서 한참을 헤맸다. 우선 dp문제인..

문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 코드 My answer n=int(input()) d=[0]*(n+1) d[1]=1 if(n>=2): d[2]=3 for i in range(3,n+1): d[i]=d[i-1]+(2*d[i-2]) print(d[n]%10007) Another answer a=b=1 for i in range(int(input())): a,b=b,2*a+b print(a%10007) 풀이 우선 관계식 자체는 위의 코드처럼 d[i]=d[i-1]+d[i-2]*2가 나오게 된다. 규칙이 나온 이유는 위에 첨부된..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 코드 My answer n=int(input()) d=[0]*(n+1) d[1]=1 if(n>=2): d[2]=2 for i in range(3,n+1): d[i]=d[i-1]+d[i-2] print(d[n]%10007) Another answer a=b=1 for i in range(int(input())): a,b=b,a+b print(a%10007) 풀이 이번 동적프로그래밍 문제는 피보나치 수열이랑 규칙이 똑같았다. 아래 코드는 파이썬이라서 가능한 코드인 것 같다. a,b=..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 My answer n=int(input()) d=[0]*(n+1) d[1]=0 for i in range(2,n+1): tmpa,tmpb=n,n if(i%2==0): tmpa=d[i//2]+1 if(i%3==0): tmpb=d[i//3]+1 tmpc=d[i-1]+1 d[i]=min(tmpa,tmpb,tmpc) print(d[n]) Another answer n = int(input()) li = [0]*(n+1) # 0,1,2,...,n li[1] = 0 for i in range(2,n+1) : li[i] = min((li[i//3]+i%3+1),(li[i//2]..

문제 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 My answer h,w=map(int,input().split()) if(h==1 or w==1): answer=1 elif(h=5): if(h>=3):answer=max(4,5+(w-7)) else:answer=4 print(answer) Another answer N,M=map(int,input().split()) if N==1: print(1) elif N==2: print(min(4,(M+1)//2)) else: print(max(M-2,min(4,M))) 풀이 우선 코드 설명은 h가 1이면 지금있는 칸 끝..

문제 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 코드 My answer(시간초과) First Try import sys from itertools import combinations res=[] while(1): n=int(sys.stdin.readline()) if(n==0):break tmp=[i for i in range(3,n+1) if i%2!=0] for i in range(len(tmp)): if(tmp[i]!=0): for j in range(i+1,len(tmp))..