기록방

👉 문제링크 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 n개의 돌이 있을때, ab 두 사람이 턴마다 1개 혹은 3개를 가져갈 수 있고 마지막 돌을 가져가면 패배한다. 두 사람이 완벽하게 게임을 한다고 했을때 상황을 그려보면 다음과 같다. n=1 : a >> b승리 n=2 : a b >> a승리 n=3 : a b a >> b승리 n=4 : a a a b >> a승리 홀수는 b승리, 짝수는 a의 승리라는 것을 알 수 있다. n이 최대 1000이고 시간 복잡도는 O(n)이므로, 제한시간 1초는 널널하다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOExce..

👉 문제링크 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 🔸 문제 분석 🔸 2차원 배열의 구간 합을 출력한다. 시간초과를 방지하기 위해 구간 합을 미리 계산한다. i = 1일때와 j = 1 는 1차원 배열의 구간 합 채우기 공식이 같다 : sum[i] = sum[i-1] + arr[i] 2차원 배열 구간합 배열을 채우는 공식 : sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + arr[i][j] 구하려는 인덱스의 위..

👉 문제링크 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 🔸 문제 분석 🔸 입력받은 n을 제곱수의 합으로 표현할 때 최소한의 경우의 수를 출력한다. dp 와 브루트 포스 풀이 두 가지가 가능하다. dp dp[n] 리스트는 n을 만드는데 들어가는 '제곱수 합 경우의 수의 최소값'을 저장한다. dp[0] = 0, dp[1] = 1 로 초기화한다. dp[n]을 구할 때, 1부터 j의 제곱수(j**2)가 i보다 커질때까지 반복하며 최소값을 찾는다. min_v : i에서 j**2를..

👉 문제링크 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 🔸 문제 분석 🔸 1x2, 2x1, 2x2 타일을 채우는 경우의 수를 출력한다. 점화식은 dp[n] = dp[n-1] + dp[n-2]*2 이다. 🔸 코드 🔸 arr = [1,1] for _ in range(int(input())-1): arr.append((arr[-1]+arr[-2]*2)%10007) print(arr[-1]) 🔸 코드 해석 🔸 리스트의 초기값을 1,1로 두고 점화식을 적용한다. 문제 조건에 따라 10007의 나머지로 계산한다. 🔸 end 🔸 2xn타일 1을 풀..

👉 문제링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🔸 문제 분석 🔸 타일을 채울 수 있는 경우의 수를 출력한다. 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다. 🔸 코드 🔸 n = int(input()) dp = [1,1] for i in range(1,n): dp.append((dp[-1]+dp[-2])%10007) print(dp[n]) 🔸 코드 해석 🔸 dp 리스트의 인덱스 0, 1은 1로 초기화 한다. 점화식에 따라 입력 값(n) 만큼 반복하며 dp리스트를 채운다. 값을 채울 때 문제 조건에 따라 1..