문제 https://www.acmicpc.net/problem/11727 풀이 n = int(input()) dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(dp[n]%10007) 이 문제에서 2×N을 채우는 경우의 수는 세가지로 나뉜다. 1) 2×(N-2)를 채우고 = 모양을 더하는 경우 2) 2×(N-2)를 채우고 ㅁ 모양을 더하는 경우 3) 2×(N-1)을 채운 뒤 l 모양을 더하는 경우 즉, 2×N을 채우는 경우의 수는 2×(N-2)를 채우는 경우의 2배에 2×(N-1)을 더한 값이다. N=1일때 경우의 수는 1, N=2일때 경우의 수는 3이라는 것을 기본값으로 해서 동적계획법..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]%10007) 이 문제의 정답 코드는 피보나치 수열을 구하는 방식과 동일하다. 그 이유를 살펴보자면 2×N을 채우는 경우의 수는 아래 두가지로 나뉜다. 1) 2×(N-2)를 채우고 = 모양을 더하는 경우 2)..

문제 https://www.acmicpc.net/problem/2658 2658번: 직각이등변삼각형찾기 입력된 모양이 직각이등변 삼각형을 이루는 경우에는 세 꼭짓점의 위치를 출력하고, 그렇지 않은 경우에는 0을 출력한다. 각 꼭짓점의 위치를 한 줄에 두 개의 수로 출력한다. 두 수는 하나의 빈 www.acmicpc.net 풀이 직각 이등변 삼각형을 찾는 문제이다. 해당 문제에서 나올 수 있는 직각 이등변 삼각형은 아래의 기본 모양을 각각 4방향으로 회전한 삼각형들이다. 즉 8개의 삼각형을 비교 하는 코드를 구현해주어야 한다. 처음에 풀 때 오른쪽 모양의 직각이등변 삼각형을 떠올리지 못해서 시간을 많이 잡아먹었다. 최종적으로 작성한 코드는 아래와 같다. d = [] for i in range(10): d...

문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 시간초과 때문에 꽤나 고생했던 문제이다. 처음에는 단순하게 min과 max 사이의 숫자 각각에 대해서 4,9,16...등 모든 제곱수를 나누어 보면서 제곱ㄴㄴ수를 판별했는데 이런식으로 구현하니까 시간초과가 발생하였다. #시간초과 a,b = map(int,input().split()) cnt = 0 for i in range(a,b+1): for j in range(2,i..

문제 https://www.acmicpc.net/problem/27648 27648번: 증가 배열 만들기 첫째 줄에 $N$, $M$, $K$가 주어진다. $\left(1 \le N , M \le 1\,000,1 \le K \le 100\,000 \right)$ www.acmicpc.net 풀이 sourcen, m, k = map(int,input().split()) if k>= m+n -1: print("YES") for i in range(n): for j in range(m): print(i+j+1,end=" ") print() else: print("NO") 이 문제는 단순하게 생각하면 쉽게 풀리는 문제이다. 오른쪽과 아랫쪽으로 갈수록 더 큰 숫자가 되는 배열을 만들어야 하는데, 해당 조건을 만족하..

문제 https://www.acmicpc.net/problem/16719 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 풀이 s=input() l=len(s) now =[False]*l for i in range(l): target = [] target_st=[] j=0 #가능한 경우의 수 다 구함 while j