본문 바로가기
반응형

전체 글282

백준 1041번 주사위 - C++(cpp) 풀이 1. 3면이 노출되는 주사위는 4개, 2면이 노출되는 주사위는 (8*N-12) 개, 나머지는 1면만 노출되는 주사위이다. 2. 노출되는 면의 숫자 합이 최소가 되도록 한다. 3. N=1인 경우 예외 처리를 해준다. 1. 3면이 노출되는 주사위는 4개, 2면이 노출되는 주사위는 (8*N-12) 개,나머지는 1면만 노출되는 주사위이다. 윗면의 네 꼭짓점에 위치한 주사위는 세 면이 노출된다. 그리고 8개의 모서리에서 꼭짓점을 제외한 곳에 위치한 주사위들은 총 두 면이 노출된다. 나머지 주사위들은 한 면만 노출된다. 2. 노출되는 면의 숫자 합이 최소가 되도록 한다. 먼저 3면이 노출되는 주사위부터 생각해보자. 노출되는 3면의 종류는 꼭짓점의 개수와 같으므로 8가지이다. (AED, ABD, ACE, ABC, F.. 2022. 4. 4.
백준 22968번 균형 - C++(cpp) 풀이 1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자. 2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-1) + f(h-2) + 1 3. f(h) ≤ V인 h 중 최댓값을 찾는다. 1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자. AVL 트리에서는 모든 부분 트리가 AVL 트리이다. 따라서 재귀적인 방법을 떠올릴 수 있다. 먼저 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값을 f(h)라고 정의하자. 2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-.. 2022. 4. 1.
백준 1103번 게임 - C++(cpp) 풀이 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) 1. 그래프에 사이클이 존재하면 무한번 움직일 수 있다. DFS를 이용해 사이클을 확인한다. 무한번 움직일 수 있는 경우는, 그래프에 사이클이 존재하는 경우이다. DFS를 사용해서 사이클 존재여부를 체크한 후, 존재한다면 바로 -1을 출력해준다. 2. dp(r, c) = (r, c) 위치에서 시작했을 때 최대 이동 횟수라고 하면, dp(r, c) = 1 + max(dp(상), dp(하), dp(좌), dp(우)) dp(r, c) = (r,c) 위.. 2022. 3. 30.
백준 1038번 감소하는 수 - C++(cpp) 풀이 1. 0-9 중 사용할 수들을 선택한 뒤, 큰 수부터 차례로 나열하면 감소하는 수가 만들어진다. 2. 따라서 감소하는 수의 총개수는 2^10-1 = 1023개 3. 감소하는 수를 모두 구한 뒤 정렬한다. 1. 0-9 중 사용할 수들을 선택한 뒤, 큰 수부터 차례로 나열하면 감소하는 수가 만들어진다. 숫자 목록이 주어지면 해당 수들로 만들 수 있는 감소하는 수는 하나로 결정된다. 또한 항상 감소해야 하므로 같은 숫자가 두 번 이상 등장하는 일은 없다. 따라서 10개 숫자 0-9에 대해 각각을 사용할 것인지를 결정하기만 하면 감소하는 수가 결정되고, 그 감소하는 수는 선택한 숫자들을 큰 수부터 차례로 나열한 것이 된다. 2. 따라서 감소하는 수의 총 개수는 2^10-1 = 1023개 10개 숫자에 대해 사용.. 2022. 3. 29.
백준 24913번 개표 - C++(cpp) 풀이 1. 1번 쿼리가 들어오면 정후를 제외한 후보자들의 득표수 합과 최대 득표수를 매 쿼리마다 업데이트한다. 2. 2번 쿼리가 들어오면 [y표를 더한 후의 득표수 합이 N*(X-1) 이하이면서, y표를 더하기 전 최고 득표수가 X 미만]인지 체크한다. 1. 1번 쿼리가 들어오면 정후를 제외한 후보자들의 득표수 합과 최대 득표수를 매 쿼리마다 업데이트한다. 2번 쿼리를 수행하기 위해서는 정후를 제외한 후보자들의 득표수 합과 최대 득표수 정보가 필요하다. 1번 쿼리가 들어오면 이 두 값을 계산해두도록 한다. 2. 2번 쿼리가 들어오면 [y표를 더한 후의 득표수 합이 N*(X-1) 이하이면서, y표를 더하기 전 최고 득표수가 X 미만]인지 체크한다. 정후를 제외한 후보자들의 득표수 합을 sum, 정후의 현재 득표.. 2022. 3. 26.
반응형

티스토리툴바