백준 (223) 썸네일형 리스트형 백준 2399 - 거리의 합 www.acmicpc.net/problem/2399 C 계열 언어를 쓰면 $O(N^2)$로 뚝딱 풀 수 있지만 파이썬으로 풀어보았다. 풀이 점과 점 사이 거리를 누적합으로 저장하면 $O(N)$으로 모든 쌍의 거리를 저장할 수 있다. 점들의 좌표들이 정렬된 배열 ar에서 $f(i - 1)$이 ar[i - 1]과 이전 점들의 거리 합을 나타낼 때 ar[i]와 이전 점들의 거리 합을 구하는 점화식은 $f(i) = f(i - 1) + (ar_{i} + ar_{i - 1}) \times i$이다. i가 1씩 증가할 때마다 이전 점들과 ar[i] 사이의 거리를 구하기 위해 $(ar_{i} + ar_{i - 1})$를 지금까지 거쳤던 점들의 개수만큼 더해줘야 한다는 사실을 생각하면 $(ar_{i} + ar_{i - .. 백준 7562 - 나이트의 이동 www.acmicpc.net/problem/7562 각 테스트 케이스마다 bfs를 수행하여 나이트의 최소 이동 횟수를 찾으면 된다. 전체 코드 더보기 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include using namespace std; using ll = long long; int t; int n; int a, b, c, d; int cnt; bool vst[300][300]; int n.. 백준 2315 - 가로등 끄기 www.acmicpc.net/problem/2315 점화식 하는 방법을 익히면 어렵지 않게 풀 수 있다. 마징가가 가로등을 끄는 시간은 0이기 때문에 어떤 가로등을 끄지 않고 지나가면 최적해에 도달할 수 없음을 그리디 속성으로 이해할 수 있다. 따라서 마징가가 어떤 구간을 지나간다고 하면 구간에 속한 가로등은 모두 꺼진 상태여야 한다. 마징가가 어떤 구간에 속한 가로등을 모두 끄고 나면 구간의 끝에 위치하게 되므로 다음과 같은 점화식을 세울 수 있다. $f(l, r, direction) = $ l번부터 r번 가로등까지 끈 상태이고 마징가가 direction 방향 끝에 있을 때 소비된 전력양의 최솟값 전력 소비량 계산 누적합으로 구간 전력 소비량을 저장하면 특정 구간에서 소비되는 전력의 소비량을 $O(1).. [ICPC] 백준 11497 - 통나무 건너뛰기 www.acmicpc.net/problem/11497 풀이 가장 높은 통나무를 가운데 세운다! 짝수개면 상위 2개 통나무를 가운데 세운다! 그리고 남은 통나무들을 내림차순으로 양 옆으로 배치해나가면 원형을 고려했을 때의 최적해를 구할 수 있다! 양 옆에 통나무를 놓을 때 발생하는 높이차가 더 적은 경우로 배치하여 최적 부분 구조가 깨지지 않도록 하자! 구현 통나무를 양 옆에 붙이는 행위를 덱으로 구현하였다. 전체 코드 더보기 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56.. [KOI] 백준 10835 - 카드게임 www.acmicpc.net/problem/10835 다음 가지치기로 얻을 수 있는 최대 점수를 동적계획법으로 구하면 된다. 왼쪽 카드를 버렸을 때 / 양쪽 카드를 버렸을 때 / 오른쪽 카드를 버릴 수 있을 경우 버리고 점수를 얻었을 때 전체 코드 더보기 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 32 33 34 35 36 37 38 39 #include using namespace std; int n; int l[2000], r[2000]; int dp[2000][2000]; int memo(int ldx, int rdx); int main() { memset(dp, -1, sizeof dp); .. 이전 1 ··· 24 25 26 27 28 29 30 ··· 45 다음
