그냥 하는 노트와 메모장

* BOJ 2543 초고속철도[분류: 다이나믹 프로그래밍] [풀이] 인접한 로봇끼리는 반드시 통신이 가능해야 한다는 점을 유심히 보자. 만약 어떤 로봇 a가 b, c, d, w와 겹치는 상황을 생각해보자. 1. [a에 설치하는 경우] 나머지 b,c,d,w,에 설치할 수도 있고 안할 수도 있다. 2. [a에 설치하지 않는 경우] b,c,d,w에 모두 통신을 설치해야만 한다. [순서도] 1. 먼저 구간 시작 좌표를 기준으로 로봇들을 정렬하자. 정렬하는 이유는 시작 좌표가 낮은 로봇을 기준으로 설치하느냐 마느냐를 결정하여 이후에 있는 로봇에 영향을 미치는 데에 있어 계산하기 용이하기 때문이다. 2. 오름차순으로 방문하며 현재 p번째 로봇에 대해 통신장비를 설치할지말지를 결정해야 한다. 3. 설치한다면 p번째 ..