Algorithm/BOJ11 1965번 상자넣기 문제의 해결법 앞에 상자를 넣기 위해서는 뒤에 상자가 앞의 상자보다 더 커야 한다. 최고로 많이 넣을 수 있는 문제를 푼다고 하면, 최장증가부분수열의 문제와 같다고 볼 수 있다. 예제 1번 박스부터 시작하여 1번 박스보다 큰 모든 박스에게 +1해준다. 6번 박스보다 작은 것들은 1번 박스때의 숫자를 가지고 오고 큰 숫자들은 +1이거나 이전 박스까지 센 숫자 중 큰 것을 넣어준다. 점화식 $$dp[i][j] = \begin{cases} max(dp[i][i]+1, dp[i-1][j]), & \text{if }n\text{ box[i] < box[j]} \\ dp[i-1][j], & \text{if }n\text{ box[i]} \ge \text{box[j]} \end{cases} $$ 소스코드 public.. 2021. 5. 19. 공유기 설치 - 2110번 풀이 방법 L이 증가 할수록 공유기의 개수를 감소한다. 만약 크기가 L이고 i번째에 공유기를 설치했다면 다음 공유기를 설치할 좌표(j)는 아래 공식과 같다. $$ X[i] + L 2019. 6. 9. 최소값 찾기 - 11003번 해결방법 세그먼트 트리로 안 풀렸다.세그먼트 트리로는 정말 힘들다그래서 우선순위큐로 풀었다. 근데 이것도 겨우겨우 시간 통과했다. 우선순위큐는 최대값을 반환하므로 최소값을 찾기 위해 {-값, index}를 input으로 받는다. priority_queue pq; // { -값, index } 그리고 최솟값의 인덱스가 i - L + 1라면, pq.top().first를 출력하고 아니라면 해당 인덱스가 나올때까지 반복한다. 전체코드 #include #include using namespace std; priority_queue pq; int N, L, A; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> N >> L; for.. 2019. 5. 19. 탑 - 2493번 해결방법 stack을 이용하여 해결 할 수 있다. stack에는 index를 넣는다. if num[stack.top()] input보다 큰 값이 stack이 나올때 까지 pop한다. -> stack이 empty라면 0을 출력 -> 아니라면 stack.top()을 출력 -> stack에 index를 푸쉬한다. else -> st.top() 출력 -> stack에 index 출력 전체소스 #include #include using namespace std; int N, num[500001]; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); stack st; cin >> N; for (int i = 1; i > num[.. 2019. 5. 19. 나머지 합 - 10986번 해결방법 SUM(0 ~ i) % M의 개수를 받는다. i > M; while(N--) { cin >> a; sum += a; num[sum % M]++; } ll ans = num[0]; for (int i = 0; i < M; ++i) ans += (num[i] * (num[i] - 1)) / 2; cout 2019. 5. 19. 1931번 - 회의실 배정 해결방벙 그리디 방법으로 해결하였다. 증명 회의실을 가장 많이 사용 할 수 있는 경우는 1. 끝나는 시간이 빠른 것, 2. 시작시간이 빠른 것 순으로 정렬 하고 가능한 시간의 개수를 탐색하면 된다. $$ END_{i} >= END_{j} \ (단, \ i는\ 가장\ 빨리\ 끝나는\ 회의, \ j는\ i제외한\ 회의, \ END는\ 이후\ 가능한\ 회의의\ 개수)$$ 그러므로 끝나는 회의의 수가 가장 빠르면 더 많은 회의를 할 수 있다. 전체 소스 #include #include #include using namespace std; int N; vector time; bool cmp(pair a, pair b) { if (a.second == b.second) return a.first < b.first;.. 2019. 5. 5. 6549번 - 히스토그램에서 가장 큰 직사각형 해결방법 라인 4번 문제와 흡사한 문제로 보인다. 이상하게 요즘 문제들이 쉬운듯 어려운 문제가 많이 보이는데 여러가지 자료구조를 안써보았기 때문이라고 생각한다. 무작위로 풀면서 사고력을 길러야 겠다. 내가 푼 방법은 2가지 이다. segment tree + conqure & divide방법과 stack방법이다. Segment Tree + conquare & divide Segment Tree는 각 구간에서 가장 높이가 낮은 index를 저장해준다. int init(int leftn, int rightn, int node) { if (leftn == rightn) return tree[node] = leftn; int mid = (leftn + rightn) / 2; int leftv = init(left.. 2019. 5. 2. 동전0 - 11047번 해결방법 알고리즘은 그리디를 사용하였다. 하지만 그리디를 사용해도 최적인지 증명과정이 필요하다. 증명 문제에서는 i개의 동전이 있고, 오름차순으로 주어진다. N을 금액이라고 할 때 동전이 N보다 작다면 항상 아래와 같다. $$ N / C_{i} K >> N; int ans = 0; for (int i = 0; i > c[i]; for (int i = K - 1; i >= 0; --i) if (N >= c[i]) { ans += N / c[i]; N -= (N / c[i] * c[i]); } cout 2019. 4. 29. 동물원 - 1309번 해결방법 O을 배치한 경우, X를 배치 하지 않은 경우라고 할 때 O X | X O | X X 3가지 경우의 수로 둘 수 있다. 그래서 dp를 N * 3개의 배열을 두고 시작하였다. int dp[100001][3] 점화식은 어떻게 될까? 점화식도 3가지로 나눌 수 있다. 만약 O X경우라면 이전의 경우의 수는 X O | X X가 되어야만 하기 때문에 아래와 같아진다. 나머지도 똑같은 방식으로 구해본다면 점화식을 구할 수 있다. $$ dp[i][0] = dp[i-1][1] + dp[i-1][2] $$ $$ dp[i][1] = dp[i-1][0] + dp[i-1][2] $$ $$ dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] $$ 전체코드 #include using n.. 2019. 4. 29. 3980번 - 선발명단 해결방법 bitmask dp로 해결하였다.dp를 2차원 배열로 (position, state)를 담을 수 있게 정의하였다. int dp[11][1 > t) % 2 == 0은 t라는 포지션이 0일 경우 아직 배정이 안됬으므로 배정을 해야한다는 조건이다. 더해서 포지션의 능력치가 0이 되면 안되기 때문에 s[p][t] != 0아닌 것도 포함해줘야 한다. sub를 둔 이유는 조건에 맞는 포지션이 없을 경우 -1를 리턴하는데, 이 경우는 포지션을 모두 배정하지 못한 경우의 수므로 제외시켜줘야 한다. if ((state >> t) % 2 == 0 && s[p][t] != 0) { int sub = solution(p + 1, state | 1 t) % 2 == 0 && s[p][t] != 0) { int sub .. 2019. 4. 20. 1102번 - 발전소 해결방법 해당 문제는 bitmask dp로 풀었다. bit가 켜지면 발전소가 켜진 것이고, bit가 꺼지면 발전소가 꺼진 것이다. bitmask dp로 푼 이유는 a번째 발전소가 j번째 가동시킬때와 b번째 발전소가 j번째 발전소를 가동시킬때가 다르기 때문이다. 문제를 풀 때 유의할 점은 0개 이상일 경우이다. 0개 이상일 경우 0을 리턴해야하지 -1를 리턴하게 하면 안된다. int dp[1 > i) % 2 == 1) cnt++; if (cnt >= T) return 0; T보다 작다면 비트가 0인 수를 찾은 다음 비트가 1인 수들 중에서 비용 값을 더해주고 0비트를 1로 바꿔 재귀시켜준다. for (int i = 0; i > i) % 2 == 0) { // 안켜진 발전.. 2019. 4. 19. 이전 1 다음
