백준34 [BOJ]14501번: 퇴사 문제: https://www.acmicpc.net/problem/14501 모든 경우를 다 구해봐야 하므로 DP 문제입니다. 제가 세운 점화식은 다음과 같습니다. dp[day][revenue]: 특정 DAY까지 revenue를 벌었을 때의 상태를 저장했습니다. dp[day][revenue] = max(특정 day 일을 하거나, 특정 day 일을 안하거나) 이렇게 나눌 수 있습니다. 특정 day 상담 일을 한다면 다음 날짜는 day 상담기간만큼 JUMP 할 것이고 특정 day 상담 일을 안한다면 day + 1 상담을 할 지 말지 결정하는 로직으로 넘어가면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ14501.cc 2020. 7. 2. [BOJ]12837번: 가계부 (Hard) 문제: https://www.acmicpc.net/problem/12837 쿼리랑 N 제한이 큽니다. O(NQ)에 처리하면 터집니다. 구간합, 갱신 쿼리를 O(logN)에 처리하기 위해 세그먼트 트리로 해결합니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ12837.cc 2020. 6. 17. [BOJ]1018번: 체스판 다시 칠하기 문제: https://www.acmicpc.net/problem/1018 시뮬레이션 문제입니다. N,M 제한이 작으므로 체스판의 시작점이 될 수 있는 모든 점에서 01010101 10101010 ... 체스판과 10101010 01010101 ... 체스판을 비교하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1018.cc 2020. 6. 3. [BOJ]17490번: 일감호에 다리 놓기 문제: https://www.acmicpc.net/problem/17490 UNION & FIND 문제입니다. M개의 공사구간이 있으면 강의동은 M개의 컴포넌트로 나뉘게 됩니다. 1. M개의 컴포넌트로 나누기 (O(N)) 2. 각 컴포넌트마다 다리를 놓는데 최소비용인 강의동 구하기(O(N)) 3-1. M개의 컴포넌트의 각 최솟값들의 합 K 이면, NO 연결상태는 graph[N][2]를 통해 표현하였습니다. graph[idx][0] = 1이면, idx번째 강의동이 idx-1 강의동과 끊어져 있음. graph[idx][1] = 1이면, idx번째 강의동이 idx+1 강의동과 끊어져 있음. (단, 원형이므로 0번째 강의동과 N-1번째 강의동의 연결관계는 반대로 처리해줘야 합니다) 끝으로 예외 처리해줄 것은 M 2020. 5. 28. 이전 1 ··· 4 5 6 7 8 9 다음
