개인공부1221 [백준] 3933번 : 라그랑주의 네 제곱수 정리 (C++) 3933번 : 라그랑주의 네 제곱수 정리 문제) 양의 정수는 많아야 4개의 제곱수로 표현할 수 있다고 한다. 이 이론을 라그랑주의 네 제곱수 정리라고 한다. 이 정리는 조제프루이 라그랑주가 1770년에 증명했다. 우리는 이 이론을 증명하거나 새로운 이론을 발견할 필요는 없고, n이 주어졌을 때 4개 이하의 양의 제곱수의 합으로 n을 만들 수 있는 경우의 수를 구하려고 한다. 경우의 수를 구할 때 제곱수의 순서가 바뀌는 경우는 같은 경우로 본다. 따라서 3^2 + 4^2 과 4^2 + 3^2는 같은 경우이다. N이 25일 때 4개 이하의 제곱수의 합으로 표현 할 수 있는 경우는 1^2 + 2^2 + 2^2 + 4^2, 3^2 + 4^2, 5^2 이렇게 3가지이다. 입력 : 입력은 최대 255줄이다. 각 줄.. 2024. 3. 8. [알고리즘] DP (Dynamic Programming) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. DP는 두가지 종류가 있다. 탑다운 DP 바텀업 DP 그 중 탑다운 DP에 대해 알아보도록 하자. 0. 백트래킹 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 위 문제를 백트래킹을 이용해 풀어보자. 위와 같은 풀이가 나올 것이다. 그렇다면 이번엔 다음의 문제를 봐보자. https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며,.. 2024. 3. 7. [백준] 1107번 : 리모컨 (C++) 1107번 : 리모컨 문제) 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 : 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘.. 2024. 2. 24. [백준] 24954번 : 물약 구매 (C++) 24954번 : 물약 구매 문제) 준겸이는 모험가이다. 모험을 떠나기 위해서는 철저한 사전 준비를 갖추어야 한다. 준겸이는 모험을 떠나기 전 N종류의 물약을 모두 구매하려고 한다. 물약 상점에 들른 준겸이는 각 물약이 1번부터 N번까지 번호가 매겨져 있다는 것을 알아냈다. 그런데, 물약 상점에서는 오늘 특별한 이벤트를 하고 있었다. 특정 물약을 구매하면, 어떤 다른 물약들을 할인해준다는 것이었다. 원래 i번째 물약의 가격은 동전 c_i개이다. 만약 i번째 물약을 구매하면, p_i종류의 다른 물약의 가격이 내려간다. 할인은 중첩된다. 예를 들어 1번 물약을 구매하면 3번 물약의 가격이 동전 1개만큼 할인되고, 2번 물약을 구매하면 역시 3번 물약의 가격이 동전 2개만큼 할인된다고 하자. 그러면 두 물약을 .. 2024. 2. 24. 이전 1 2 3 4 5 6 7 8 ··· 306 다음
