Looan's 개발 연습장

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 코드 n = int(input()) dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]) 설명 규칙을 찾아서 해결하는 dp 문제였다. n = 1 일 때, [1] n = 2 일 때, [10] n = 3 일 때, [100][101] n = 4 일 때, [1000][1001][..

문제 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 코드 n = int(input()) num = list(map(int, input().split())) dp1 = [1 for i in range(n)] dp2 = [1 for i in range(n)] for i in range(1, n): if num[i] = num[i-1]: dp2[i] = max(dp2[i], dp2[i-1] + 1) print(max(max(dp1), max(dp2))..

문제 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 코드 n = int(input()) cnt = 0 while n > 0: if n % 5 == 0: cnt += n // 5 break else: n -= 2 cnt += 1 if n < 0: print(-1) else: print(cnt) 설명 단순하게 5원부터 지급하고 나머지를 2원을 지급하려고 하면 오류가 난다. 거스름돈이 5의 배수여서 딱 나누어 떨어진다면 상관이 없지만 그렇지 않다면 2를 우선 빼주어서 계산을 해야 한다. 2를 빼다가 음수로 넘어가서 n이 음수가 된다면 -1을 출력하고 그렇지 않다면 결..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 코드 li = [0 for i in range(101)] li[1],li[2],li[3] = 1, 1, 1 for i in range(4, 101): li[i] = li[i-2] + li[i-3] t = int(input()) for _ in range(t): n = int(input()) print(li[n]) 설명 다이나믹 프로그래밍으로 규칙을 찾아서 구현을 하는 문제이다. 4번째 삼각형부터,..