DP40 [백준] 16395번 : 파스칼의 삼각형 – JAVA [자바] https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 문제 문제 풀이 백준 16395번 파스칼의 삼각형은 실버 5 난이도의 수학, 그리고 DP 문제이다. 이 문제는 DP를 이용해서 파스칼의 삼각형을 만들기만 하면 된다. 그리고 정수 n과 k가 주어지는데 n번째 행의 k번째 수를 출력해주면 끝나는 문제이다. 우선 파스칼의 삼각형은 다음과 같이 생겼다. 이를 2차원 DP 테이블로 한번 만들어 볼 것이다. 우리는 n번째 줄까지 계산을 해야 하.. 2022. 4. 21. [백준] 14606번 : 피자 (Small) – JAVA [자바] https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 문제 문제 풀이 백준 14606번 피자 (Small)은 실버 4 난이도의 수학, 그리고 DP 문제이다. 이 문제는 그리고 2017 아주대학교 프로그래밍 경시대회 (APC) Division 2에 나온 B1번 문제였다. 이 문제는 간단한 점화식으로 푸는 게 가능하고 n의 범위가 워낙 작아서 꼭 DP를 이용해서 풀 필요도 없다. 우선 문제에서 피자판의 개수 n이 주어진다. n의 범위는 1부.. 2022. 4. 20. [백준] 14916번 : 거스름돈 – JAVA [자바] https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 문제 풀이 백준 14916번 거스름돈은 1로 만들기와 비슷한 DP 문제이다. 이 문제에서는 입력으로 돈 n원이 주어지고 2원짜리 동전과 5원짜리 동전으로 최소의 동전을 써서 거스름돈을 주어야 한다. 그리고 이 돈 n원을 거슬러 줄 수 없으면 -1을 출력하면 된다. 우선 n원을 거슬러 줄 수 없다는 것은 2원과 5원짜리 동전으로 만들 수 없는 돈을 뜻한다. 1 원하고 3원만 거슬러 줄 수 없다. 나머지 돈들은 2 원하고 5원을 조합하면 만들 수 있다. 우선 int형 배열 dp를 만들고 dp [1]부터 dp [5].. 2022. 4. 14. [백준] 9711번 : 피보나치 – JAVA [자바] https://www.acmicpc.net/problem/9711 9711번: 피보나치 첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 P와 Q가 주어진다. www.acmicpc.net 문제 문제 풀이 백준 9711번 피보나치는 실버 2 난이도의 DP 문제이다. 그중에서도 피보나치와 나머지를 이용해서 푸는 문제이다. 이 문제에서는 테스트 케이스 T가 주어지고 테스트 케이스마다 정수 p와 q가 주어진다. 그리고 각 테스트 케이스에서 p번째 피보나치 수를 q로 나눈 나머지 값을 출력해주면 된다. 이 문제는 얼핏 보면 되게 쉬워 보인다. 하지만 이 문제의 정답 비율은 35.903% 밖에 되지 않는다 (2022년 4월 14일 기준). 아마도 BigInteger를 안 써서 그런 .. 2022. 4. 14. 이전 1 2 3 4 5 6 ··· 10 다음 반응형
