펭로그

문제링크 : https://noj.am/9095 어떤 숫자 N을 1, 2, 3 더하기로 나타내는 방법은 다음과 같다.[1] - 1개1 [2] - 2개1+1 → [1]+12 [3] - 4개1+2 → [1]+21+1+1, 2+1 → [2]+13 [4] - 7개 (1+2+4)1+3 : [1]+3 → [1] + 31+1+2, 2+2 → [2] + 21+2+1, 1+1+1+1, 2+1+1, 3+1 → [3] + 1 [5] - 13개 (2+4+7)1+1+3, 2+3 → [2] + 31+2+2, 1+1+1+2, 2+1, 3+2 → [3] + 21+3+1, 1+1+2+1, 2+2+1, 1+2+1+1, 1+1+1+1+1, 2+1+1+1, 3+1+1 → [4] + 1 위와 같이 시뮬레이션을 해보면 DP[N] = DP[N-..

문제링크 : https://boj.kr/6359 DP 문제라고 한다.왜 DP 문제인지는 잘 모르겠지만 DP로 풀지 않으면 정말 쉽게 풀린다. N이 5라고 가정하고 시뮬레이션을 해보자.0은 문이 닫힌 상태를 1은 문이 열린 상태를 의미한다. 맨 처음0 0 0 0 0 1라운드1 1 1 1 1 2라운드1 0 1 0 1 3라운드1 0 0 0 1 4라운드1 0 0 1 1 5라운드1 0 0 1 0 이쯤 하면 규칙을 찾을 수 있다.각 라운드에 해당하는 숫자만큼의 배수를 찾아서 1 → 0 / 0 → 1 으로 바꿔주면 된다. 12345678910111213141516171819202122232425262728// BOJ 6359 만취한 상범#include #include using namespace std; int ma..

문제링크 : https://boj.kr/2805 1. 동적계획법(DP)을 이용한 풀이법 : 시간복잡도 O(N)나무의 길이가 제일 큰 것부터 시작하여 한단계씩 내려오면서 누적 합이 입력에서 주어진 값보다 클 때까지 구하는 방법으로 풀었다.입력 받은 값들을 내림차순으로 정렬하고 맨 첫번째 인덱스에 해당하는 값부터 시작하여 1씩 높이를 빼가면서 계산했다. 나무의 높이(arr[N])가 기준 높이(result)보다 높은 부분 까지만 인덱스를 탐색하고 기준 높이 이하(arr[N] - result)가 0 이하인 값들)가 나오면 현재 누적 잘린 나무들의 합이 정답보다 작다면 계속 루프를 진행한다.이때, 높이를 1씩 빼게되면 현재까지 진행해왔던 나무들의 높이가 각각 1씩 추가되기 때문에 sum += ptr 구문을 넣어 ..