Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 세그먼트 트리
- 구간합
- 점수 따먹기
- 크루스칼
- Naver Cloud
- mongodb
- mst
- 누적합
- 21921
- redis
- 16985
- NCP
- 민준이와 마산 그리고 건우
- BOJ
- 정렬
- 다익스트라
- 17503
- 최소신장트리
- 맥주 축제
- gorilla/mux
- c++
- 이분 탐색
- dfs
- SWEA
- golang
- 구현
- DP
- 11659
- 백준
- 시뮬레이션
Archives
- Today
- Total
목록1749 (1)
Gi-Log
백준(BOJ) 14916 거스름돈 C++ 풀이
문제 링크: https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 누적합, 다이나믹 프로그래밍 처음에는 만들 수 있는 모든 부분 행렬을 구하고, 각 부분 행렬 내 원소의 총 합 중 최대값을 구하는 방법에 대해서 생각해봤다. 부분 행렬을 결정하는 것은, 부분 행렬의 "좌측 상단"과 "우측 하단" 2가지 이다. 좌측 상단을 알고 있다면, 부분 행렬의 가로 길이와 세로 길이를 통해 우측 하단의 좌표를 구할 수 있다. 따라서 좌측 상..
카테고리 없음
2021. 9. 15. 22:41