본문 바로가기

다이나믹 프로그래밍7

[백준 9655/javascript] 돌 게임 다이나믹 프로그래밍 문제 경우의 수를 처음부터 세어보면 Math.min(arr[i - 1] + 1, arr[i - 3] + 1) 위와 같은 점화식을 얻을 수 있다 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net let input = []; const readline = require("readline").createInterface({ input: process.stdin, output: process.stdout, }); readline.on("line", (line) => { input.push(line); }); readline.on("close", () =>.. 2022. 10. 1.
[백준 14606/javascript] 피자 1부터 경우의 수를 세보면 1일때 0 2일때 1 3일때 3 4일때 6 임을 알 수 있다 위 결과와 n개일 때 n-1 개와 1개로 나눌때를 생각해보면 n-1 개도 각각 나눠질수 있다는걸 생각하면 f(n) = (n - 1) + f(n - 1) 라는 점화식을 찾을 수 있다 결과를 배열에 아래서부터 넣어주면 된다 다이나믹 프로그래밍 문제이다 https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net let input = []; const readli.. 2022. 9. 29.
[백준 11727/javascript] 2Xn 타일링 2 다이나믹 프로그래밍 문제 n = 1 일때부터 경우의 수를 구해서 규칙을 찾아보면 n 의 경우의 수 = (n - 1 의 경우의 수) + (n - 2 의 경우의 수) * 2 의 규칙을 갖는 것을 알 수 있다 나머지는 매 경우마다 구해주고 배열에 bottom up 방식으로 채워나가 완성해주자 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net let input = []; const readline = require("readline").createInterface({ input: p.. 2022. 9. 28.
[백준 9095/javascript] 1, 2, 3 더하기 다이나믹 프로그래밍을 사용하는 문제 1,2,3까지는 직접 경우의 수를 구해보자 4부터는 각각 한단계 전인 3, 2, 1 일때의 경우의 수의 합과 같다.(1,2,3 을 더해주므로) bottom up 방식으로 구현을 위해 배열을 만들고 배열의 인덱스에 각각의 수를 올려가면서 저장해준다 인덱스로 필요한 수들만 꺼내서 계산하면 완성이다 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net let input = []; const readline = require("readline").createInterface({ input: process.stdin, o.. 2022. 9. 27.

티스토리툴바