코딩테스트/백준[Python]

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 코드 My answer from sys import stdin n = int(stdin.readline()) dp=[[0,0] for i in range(n+1)] dp[1]=[0,1] for i in range(2,n+1): dp[i][0]=dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][0] print(sum(dp[n])) Another answer a=b=1 for _ in range(int(input())-2): a,..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 코드 My answer from sys import stdin n = int(stdin.readline()) tmp=[i for i in range(1,10)] dp= [[0] * 10 for _ in range(n + 1)] dp[0]=[1,1,1,1,1,1,1,1,1,1] for i in range(1,n+1): for j in range(0,10): if(j==0): dp[i][j]=dp[i-1][j] else: dp..

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 코드 Another answer from sys import stdin n = int(stdin.readline()) stairs = [[0] * 10 for _ in range(n + 1)] stairs[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, n + 1): # 계단 수가 0으로 끝나는 경우 stairs[i][0] = stairs[i - 1][1] # 계단 수가 9로 끝나는 경우 stairs[i][9] = stairs[i - 1][8] # 계단 수가 1~8로 끝나는 경우 for j in range(1, 9): sta..

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