dp3 BOJ 2228 - 구간 나누기(DP) - tabulation, memoization https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net - 한 칸씩 넘어가면서 각 원소를 구간에 포함한 경우, 포함하지 않은 경우로 나눠서 최대합을 구하는 방식으로 풀었다. 어느 지점 i까지 구간에 포함하여 합을 구하였을 때 그 다음 구간에 추가하려면 i + 2부터 추가를 해야된다(구간이 연속되면 안된다) i 지점까지 사용한 구간의 갯수가 똑같다면 i + 2지점 이후로는 i지점까지 구한 최대합에 추가로 더해줘야하는 별개의 문제.. 2022. 6. 8. 프로그래머스 고득점 Kit 하루만에 뽀개기 - 7. 동적계획법(C++) 풀이 https://programmers.co.kr/learn/courses/30/parts/12263 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - java풀이와 C++풀이가 거의 차이점이 없어서 C++ 풀이로만 정리하였다 1. N으로 표현 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr - DP로 풀지 않고 완전탐색으로 풀었다. 문제에서 주어진 조건 N이 9 이하였기 때문에 4^9 = 2^18 = 26만밖에 안되었기 때문에, DP로만으로.. 2022. 3. 19. [boj]15723 - n단논법(Floyd Warshall, string 입출력) www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net - 플로이드 와샬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다. - 플로이드 와샬을 통해서 입력을 통해 주어진 논증 외에도 2~n단 논법을 통해서 징검다리 식으로 증명할 수 있는 논증에 대해서 차례차례 DP 스타일로 증명해 나갈 수 있다. - string 전체를 입력으로 받을 때 getline(cin, string)을 쓰는데 이전에 cin으로 입력을 받았다면 꼭 flushing을 해서 버퍼에 남아있는 '\n'을 제거 해줘야한.. 2021. 4. 1. 이전 1 다음
