'✍️ 코테 준비/Dynamic Programming' 카테고리의 글 목록 (2 Page)

[동적 계획법 1] [Python] 1904번. 01타일

2021.01.12

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 입력 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 출력 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 해결 방법 언뜻보면 어려워 보일 수 있다. 하지만 타일의 경우의 수에는 규칙이 있다. N 1 2 3 4 5 6 7 2진 수열의 경우의 수 1 2 3 5 8 13 21 피보나치와 같은 점화식을 가진다. f(n) = f(n-..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 9184번. 신나는 함수 실행

2021.01.12

www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 입력 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. 출력 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다. 해결 방법 dp를 활용한다. 해결 과정 [0][0][0] ~ [20][20][20]의 3차원 배열을 생성하고 각 조건별로 나눈다. 특정 범위 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 1003번. 피보나치 함수

2021.01.12

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 해결 방법 피보나치 재귀 함수에 관한 문제다. 0과 1이 호출되는 횟수 자체도 규칙이 있음을 알 수 있다. 0 1 2 3 4 5 6 7 0 1 0 1 1 2 3 5 8 1 0 1 1 2 3 5 8 13 위와 같이 호출되는 횟수도 (n-2) + (n-1..

[동적 계획법 1] [Python] 1904번. 01타일

[동적 계획법 1] [Python] 9184번. 신나는 함수 실행

[동적 계획법 1] [Python] 1003번. 피보나치 함수

티스토리툴바