그냥 하는 노트와 메모장

BOJ 8902 색상의 길이 [분류 : 그리디, 다이나믹 프로그래밍] [풀이] 하나의 색에 대해서만 생각해보자. 합쳐질 차선에 배치할 때 그 색상 중 가장 왼쪽에 올 수 있는 1차선의 후보와 2차선의 후보를 가려내보자. 순서상 같은 차선에서 같은 색상을 가지는 인덱스 i 3 a=5, F[0][a] -> 6 dp[a][b]=현재 1차선에서 a번째 후보와 2차선에서 b번째 후보를 사용할 수 있을 때 만족하는 최소 거리 (거리를 계산해야하는 색의 수) 나는 후보를 하나씩 사용하면서 거리를 계산했다. 현재 후보군 위치가 (a, b)이므로 이 이전에 사용한 데이터를 가지고 현재 어떤 색상을 쓰고 있는지(이하 usedCnt) 또 그 색상을 모두 배치 했는지(이하 doneCnt)을 알 수 있다. 각 색마다 가장 왼쪽..

BOJ 1226 국회 [분류 - 다이나믹 프로그래밍, 그리디] [풀이] 당을 하나씩 추가하면서 전체의 절반을 초과하는 경우를 봐야한다. $$a_i=의석수$$ $$total=\sum_{i=1}^{n} a_i$$ $$ half=\lfloor{total/2}\rfloor $$ [접근] 0부터 half까지 순회하면서 현재 좌석수를 더해줌으로 절반을 초과하는지 확인하면된다. [그리디] 단, 좌석수 기준 비오름차순으로 정렬한 데이터를 가지고 추가해야한다. 조건에서 보면 현재 좌석 수를 x로 구성했을 때 x를 만들기 위해 연합된 당들 각각 하나를 빼면 좌석수가 절반 이하이어야만 한다. 현재 당의 좌석수가 ci라고 할때 현재 당을 제외한 나머지 당으로 half를 구성했다고 치자. 그러면 half + ci도 정답 후보가..

* BOJ 1797 균형잡힌 줄서기 [분류 - 정렬, 그리디] 1. 브루트포스로 계산하기에는 O(N^2)은 시간적으로 부담이되기에 일단 x축을 기준으로 정렬한다. 2. x좌표가 작은 값에서 큰 값으로 순회를 시작하는데, 여자면 -1을 할당하고 남자면 1을 할당하여 누적합을 구한다. 이 때 순회하다가 이전에 나왔던 누적합(bef)이 존재한다면 현재와 bef를 비교하여 x좌표가 얼마나 차이가 있는지 계산한다. 이 값 중에 가장 큰 값을 출력해주면 된다.※ 이 때 누적합이 최초로 등장한 값만 저장해주면 된다. 문제에서 요구하는 것은 x 간격이 가장 큰 것을 원하므로 임의의 누적합이 어디서 최초로 등장했는지를 저장해두고 나중에 다시 이 누적합이 나오면 그것이 곧 최대 간격의 후보를 의미한다. #include #..