본문 바로가기

전체 글282

백준 12036번 Dance Around The Clock - C++(cpp) 풀이 1. 어떤 수 N이 짝수라면 양옆은 항상 홀수이고, 어떤 수 N이 홀수라면 양옆은 항상 짝수이다. 2. 어떤 수 N의 오른쪽 수는 항상 N의 왼쪽 수보다 2 작다. 3. K가 짝수인 경우 한 턴이 지나면 왼쪽 번호가 2 커지고, K가 홀수인 경우에는 2 작아진다. 1. 어떤 수 N이 짝수라면 양옆은 항상 홀수이고, 어떤 수 N이 홀수라면 양옆은 항상 짝수이다. 짝수와 홀수를 짝지어 자리를 바꾸기 때문에 턴이 계속되어도 항상 짝수 홀수가 번갈아서 배치되는 규칙이 있다. 2. 어떤 수 N의 오른쪽 수는 항상 N의 왼쪽 수보다 2 작다. 그리고 또 어떤 수의 오른쪽 수 = 왼쪽 수 - 2라는 규칙이 있다. 3. K가 짝수인 경우 한 턴이 지나면 왼쪽 번호가 2 커지고, K가 홀수인 경우에는 2 작아진다. 위에.. 2022. 3. 21.

백준 12969번 ABC - C++(cpp) 풀이 1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K + (S에 포함된 X보다 큰 문자의 수)이다. 2. dp(a, b, c, k) = 'A', 'B', 'C'를 각각 a, b, c개 가지고 있으면서 오름차순 쌍이 k개인 문자열의 존재 여부 3. 따라서 'A'로 시작하는 경우, 'B'로 시작하는 경우, 'C'로 시작하는 경우를 모두 고려하면, dp(a, b, c, k) = dp(a-1, b, c, k-b-c) 또는 dp(a, b-1, c, k-c) 또는 dp(a, b, c-1, k) 1. 오름차순 쌍이 K개인 문자열 S 앞에 어떠한 문자 X를 붙여 문자열 XS를 만들었을 때, 문자열 XS가 가진 오름차순 쌍의 수는 K +.. 2022. 3. 20.

백준 3259번 PEOPLE - C++(cpp) 풀이 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. N명의 거짓말쟁이 여부를 결정하는 모든 경우는 총 2^N가지이다. 각 경우가 유효한지 체크하는 데 O(2N)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(2N*2^N)이다. N이 최대 20밖에 되지 않으므로 브루트포스로도 해결이 가능하다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 어떠한 경우가 유효한지 체크하려면, 해당 경우를 기준으로 모든 사람들의 진술에 모순이 존재.. 2022. 3. 18.

백준 1700번 멀티탭 스케줄링 - C++(cpp) 풀이 1. 이미 꽂혀있다면 스킵한다. 2. 빈 자리가 있다면 빈 자리에 꽂는다. 3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다. 1. 이미 꽂혀있다면 스킵한다. 이미 꽂혀있다면 스킵해도 된다. 2. 빈 자리가 있다면 빈 자리에 꽂는다. 빈 자리가 있다면 빈 자리를 채우면 된다. 3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다. 문제는 빈 자리가 없는 경우인데, 이때는 가장 나중에 사용할 것을 뽑는 것이 최적이다. 반대로 가장 나중에 사용할 용품이 아닌 것을 뽑았다고 치면, 그 전기용품 차례가 왔을 때 어차피 기존 것을 하나 뽑고 새로 꽂아야 하기 때문이다. #include #include #include using namespace std; const int MAX = 101; int N, K.. 2022. 3. 14.

백준 14891번 톱니바퀴 - C++(cpp) 풀이 1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다. 2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다. 1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다. 인접하면서 맞닿는 극이 반대인 톱니바퀴로만 전이가 일어날 수 있으므로, 그런 톱니바퀴들끼리만 간선으로 연결되어있다고 생각하자. 2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다. 회전 쿼리가 주어질 때마다 DFS로 회전의 전이를 시뮬레이션하면 된다. 전이는 회전하기 전의 상태를 기준으로 결정되기 때문에 rotate를 재귀 호출 이후에 실행해.. 2022. 3. 11.

이전 1 ··· 31 32 33 34 35 36 37 ··· 57 다음

티스토리툴바