본문 바로가기
반응형

Problem Solving/BOJ228

백준 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.
백준 12169번 Infinite House of Pancakes - C++(cpp) 풀이 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 2. 총 i번의 노말 턴을 진행하는 경우, 스페셜 턴을 전부 진행한 뒤 다이너들의 접시에는 전부 i개 이하의 팬케이크가 남아있어야 한다. 3. 총 i(1 ≤ i ≤ 1000) 번의 노말 턴을 진행하는 모든 경우를 고려하여 최솟값을 찾는다. 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 노말 턴과 스페셜 턴을 한 번씩 진행해야 한다고 하자. 노말 턴 → 스페셜 턴의 순서로 진행할 때보다, 스페셜 턴 → 노말 턴의 순서로 진행할 때 같거나 더 적은 시간이 든다. 현재 다이너가 d명 있다.. 2022. 3. 25.
백준 14791번 Tidy Numbers - C++(cpp) 풀이 1. 10^18 이하의 tidy number를 모두 구한다. 2. tidy number들을 정렬한 뒤, N의 upper bound를 구한다. 3. tidy_numbers[upper_bound-1]이 N 이하인 가장 큰 tidy number이다. 1. 10^18 이하의 tidy number를 모두 구한다. 10^18 이하의 tidy numbers는 총 4,686,824개이다. 생각보다 많지 않으므로 이것을 모두 구해주자. tidy number를 문자열로 생각하면, 모든 부분 문자열 또한 tidy number이다. 따라서 길이가 len인 tidy number X에, X의 마지막 문자보다 크거나 같은 문자를 덧붙이면 길이가 len+1인 tidy number를 만들 수 있다. 이러한 사실을 사용해서 재귀를 통해.. 2022. 3. 23.
반응형

티스토리툴바