반응형 분류 전체보기252 [백준][Python] 11727번 2×n 타일링 2 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 코드 n = int(input()) dp = [0]*(n+2) dp[1] = 1 dp[2] = 3 for i in range(3,n+1): if i % 2 == 0: dp[i] = dp[i-2] * 4 - 1 else: dp[i] = dp[i-2] * 4 + 1 print(dp[n] % 10007) 설명 규칙을 찾기가 되게 어려웠다.. 일단 그 전에 푼 2×n 타일링과 달리 2×2 타일이 추가되었기 때문에 n이 짝수일 때와 홀수일 때의 규칙이 따로따로 존재하겠다는 생각이 들었다. 그래서 n이 .. 2022. 5. 12. [백준][Python] 11726번 2×n 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 코드 n = int(input()) dp = [0]*(n+2) dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = dp[i-2]+dp[i-1] print(dp[n]%10007) 설명 규칙을 찾으려고 n이 5일 때까지 경우의 수를 구해봤다. dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 5 dp[5] = 8 구해놓고 보니 dp[i] = dp[i-2]+dp[i-1] 이라는 규칙이 보였다. 2022. 5. 11. [백준][Python] 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 n = int(input()) dp = [0]*(n+1) dp[1] = 0 for i in range(2,n+1): dp[i] = dp[i-1]+1 if i%3 == 0: dp[i] = min(dp[i],dp[i//3]+1) if i%2 == 0: dp[i] = min(dp[i],dp[i//2]+1) print(dp[n]) 설명 2나 3으로 나누어떨어지더라도 1을 먼저 빼주는 것이 최솟값이 될 수 있으므로 모든 경우의 수를 생각해야 한다. 먼저 dp[i]의 값을 1을 먼저 빼줬을 경우의 횟수인 dp[i-1]+1로 둔다. 그다음 만약 i가 3으로 나누어떨어지면 i를 3으로.. 2022. 5. 10. [백준][Python] 17626번 Four Squares 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 코드 n = int(input()) n_list = [0]*(n+1) n_list[1] = 1 for i in range(2,n+1): j = 1 min_v = 4 while((j**2) 2022. 5. 9. 이전 1 ··· 41 42 43 44 45 46 47 ··· 63 다음 반응형
