BOJ6 최소값 찾기 - 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. 동물원 - 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. 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 다음