xy_map = [[False for x in range(101)] for y in range(101)]
area = 0
for cnt in range(4):
x1, y1, x2, y2 = map(int, input().split())
for i in range(x1, x2):
for j in range(y1, y2):
if xy_map[i][j]: continue
area += 1
xy_map[i][j] = True
print(area)
두 번째 수를 선정할 때, 첫 번째 수보다 큰 값이 들어간다면 길이가 2보다 커질 수 없다.
list[0] = n
list[1] = n + α
# list[2] = -α
len(list) = 2
그러나, 두 번째 수가 첫 번째 수와 같다면 리스트 길이는 4이 된다.
list[0] = n
list[1] = n
list[2] = 0
list[3] = n
# list[4] = -n
len(list) = 4
따라서 최대 개수의 수들을 구할 때, 두 번째 수는 첫 번째 수보다 작거나 같은 수들만 체크하면 된다.
가능한 모든 두 번째 수를 for문을 통해 순회하며 체크한다.(브루트 포스)
풀이
첫 번째 수를 n 변수에 입력받는다.
최대 길이를 가진 수들을 저장할 my_list를 선언한다.
for문을 통해 두 번째 수를 모두 검사한다.(두 번째 수 = i)
첫 번째, 두 번째 수가 정해졌을 때 조건을 만족하는 수들을 저장할 my_list를 선언한다.
while문을 통해 세 번째 수부터 my_list에 저장한다.(종료조건 : 다음 수가 음수일 때)
my_list를 다 만들면 max_list의 길이와 비교하고, 더 길면 max_list로 저장한다.
출력
코드
n = int(input())
max_list = []
for i in range(1, n + 1):
my_list = [n]
my_list.append(i)
idx = 1
while True:
next_num = my_list[idx - 1] - my_list[idx]
if next_num < 0:
break
my_list.append(next_num)
idx += 1
if len(max_list) < len(my_list):
max_list = my_list
print(len(max_list))
for i in max_list:
print(i, end=' ')
점화식을 유도해내야 하는 문제이다. 타일을 '00', 혹은 '1' 로만 붙일 수 있다. 즉, 타일을 2개 붙이는 경우와 1개 붙이는 경우가 있기 때문에, n번째 답을 구하기 위해선 n-1번째와 n-2번째 경우를 탐색해야 한다.
1) 'n - 1'번째 경우와 'n'번째 경우의 관계
만약 'n-1'개의 타일을 모든 경우의 수로 놓았다고 가정해보자. 그렇다면, 타일을 1개만 추가할 수 있으므로 '1'타일을 추가하는 경우밖에 없다. 따라서, 'dp[n] = dp[n - 1]'이 된다. *dp[n] = n개의 타일을 놓을 수 있는 모든 경우의 수
*만약 'n-1'번째 타일이 '0'타일 홀수개로 끝난다면, 'n'번째에 '0'타일 한개를 놓을 수 있다고 생각할 수 있다. 하지만, 'n-1'번째 타일을 모든 경우의 수로 놓았다는 전제 조건이 있기 때문에, 'n-1'번째 경우에는 '0'타일이 홀수개로 끝나는 경우가 없으므로 고려하지 않아도 된다.
2) 'n - 2'번째 경우와 'n'번째 경우의 관계
만약 'n-2'개의 타일을 모든 경우의 수로 놓았다고 가정해보자. 이때, 타일을 2개 추가할 수 있으므로 '00'타일을 추가하거나, '11'타일을 추가할 수 있다. 하지만, '11'타일을 놓는 경우는 'n-1'번째 경우와 중복이 되므로 제외해야 한다. 따라서, 'dp[n] = dp[n - 2]'가 된다.
위 두 가지 경우를 합하면, dp[n] = dp[n - 1] + dp[n - 2]가 된다. 이때, 정답을 15746로 나눈 값을 출력하라는 조건이 있는데, 나머지 연산은 분배법칙이 적용되므로, (dp[n - 1] + dp[n - 2]) % 15746 = {(dp[n - 1] % 15746) + (dp[n - 2] % 15746)} % 15746 이 성립한다.
답안
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//Input
int n = scanner.nextInt();
int[] dp = new int[n + 1];
//Catch array index out of bounds
if(n == 1) {
System.out.println(1);
return;
}
if(n == 2) {
System.out.println(2);
return;
}
//Initial condition
dp[1] = 1;
dp[2] = 2;
//Recurrence relation
for(int i = 3; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
dp[i] %= 15746;
}
//Output
System.out.println(dp[n]);
}
}
