1. 행복 그냥 구간 내 최대 최소 찾기 2. 화살표 그리기 각 색깔 별 벡터를 만들어서 각 벡터에 점을 저장한다. 색깔별 벡터를 오름차순 정렬해서 인접한 두 점까지의 거리만 비교해서 더하면 된다. 3. 두 로봇 시작 점과 도착 점사이의 최단 경로를 구하고 그 경로 상에서 가장 긴 간선 값을 빼면 된다. 시작 점에서 bfs를 하면서 각 점의 부모 노드를 저장하는 식으로 도착점을 찾을 때까지 구하고 도착점부터 거꾸로 부모노드를 찾으면서 올라오면 된다. 이 때 어떤 점 i의 부모 노드를 p[i] 배열에 저장하는데 그 외에 i와 p[i]사이 거리를 저장하는 배열 pd[i]도 만들어놓으면 편하다. 경로를 알기 때문에 그 사이 가장 긴 간선 값도 따로 구해주면 된다. 4. 물탱크 여러번 틀렸다. 아이디어 잡는데 ..
KOI 2017 중등부 해설
1. 방 배정하기 2019/10/03 - [koi해설] - KOI 2017 초등부 해설 2. 곡선 자르기 문제는 단순해 보였지만 아이디어를 잡는데 오래 걸렸다. 각 봉우리사이 포함관계를 확인하면 쉽게 풀리지만 그럴 경우 O(N^2)이다. 시간내에 해결하려면 O(NlogN)또는 O(N)이어야한다는 것에서 정렬 아이디어가 떠올랐다. 각 봉우리의 시작점과 끝점을 pair로 저장한다. 그 후에 pair쌍을 정렬한다. 왼쪽에서부터 하나씩 확인하는데 가장 바깥쪽의 봉우리의 오른쪽 점의 좌표(outmax), 가장 안쪽 봉우리의 오른쪽 좌표(inmax)를 저장한다. 포함하지 않는 봉우리 개수 p 포함되지 않는 봉우리 개수 q 검은 색은 이전까지의 봉우리이고 파란색은 이번에 체크할 봉우리이다. case1) a>outma..
1. 딱지 놀이(BOJ 14696) 4가지 모양의 가중치가 다르기때문에 각각의 모양에 10^9, 10^6, 10^3, 1을 대응하면 라운드 별로 A와 B의 딱지 점수를 계산할 수 있다. o(N) 2. 방 배정하기(BOJ 14697) dp[i]: i명을 세 종류 방 A,B,C 정원에 맞게 배정이 가능하면 1, 못하면 0 초기에 dp[0],dp[A],dp[B],dp[C]를 1로 설정하고, dp[i]=dp[i-a] || dp[i-b] || dp[i-c]점화식으로 풀면 된다. 3. 서울에서 경산까지(BOJ 14863) 마찬가지로 dp로 풀 수 있다. dp[citiy][time]: 현재까지 city까지 이동하고 time이상이 남았을 때 앞으로의 최대 모금액 dp의 최솟값은 -INF로 저장해놓자(time동안 이동이..
Naming Rule
# 명명법 종류1. PascalCasing대문자로 시작하는 변수명 복합어의 경우 각 단어의 첫글자가 대문자 2. CamelCasing소문자로 시작하는 변수명 복합어의 경우 두 번째 단어의 첫글자가 대문자 3. GNU Naming Convention소문자를 사용하고 복합어 사이에 '_' 사용 # Rule1. 변수●보통 camelcasing 사용 (ex) priceSum●float, double형의 변수는 앞에 f,d 써줌(ex) float fPriceSum, double dPriceSum●unsigned형이면 u로 시작(ex) int uPrice, long uPrice, float fUPrice, double dUPrice●문자형은 ch로 시작(ex) char ch, char chInput, char ch..