정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 www.acmicpc.net 1. 풀이 알고리즘 분류가 "이분 탐색"이라고 되어 있는 것을 보고 처음에 생각난 풀이는 다음과 같다. 0. 집들과..

0. 문제 주소 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 풀이 투 포인터 문제. 왼쪽과 오른쪽 포인터들을 각각 어느 조건에서 움직여야 하는지, 종결 조건은 무엇인지 순서가 항상 헷갈렸다. 생각해볼 점은 다음과 같다. 0. 왼쪽 포인터를 L, 오른쪽 포인터를 R이라 하자. 1. 주어진 배열의 수들은 모두 자연수이다. 2. 1.의 이유로 R을 오른쪽으로 옮기면, L과 R이 나타내는 구간합은 무조건 커진다. 3..