본문 바로가기
반응형

Problem Solving242

백준 24551번 일이 너무 많아... - 파이썬(Python) 풀이 1. N 이하인 자연수들 중 X의 배수인 수의 개수는 N / X개이다. 2. 포함배제의 원리를 이용하여 2개 이상의 1들로만 이루어진 수의 배수인 수들의 개수를 구한다. 2. A의 배수들로 이루어진 집합과 B의 배수들로 이루어진 집합의 교집합은 A와 B의 최소공배수들로 이루어진 집합이다. 1. N 이하인 자연수들 중 X의 배수인 수의 개수는 N / X개이다. 2개 이상의 숫자 1로만 이루어진 숫자를 약수로 가지는 수는 2개 이상의 숫자 1로만 이루어진 숫자의 배수이다. N 이하인 자연수들 중 X의 배수인 수의 개수는 N / X개이다. 2. 포함배제의 원리를 이용하여 2개 이상의 1들로만 이루어진 수의 배수인 수들의 개수를 구한다. F(X)을 X의 배수이면서 N 이하인 자연수들의 집합이라고 하면, 구해야하.. 2022. 2. 28.
백준 24508번 나도리팡 - C++(cpp) 풀이 1. 총 나도리 합을 sum이라고 하면, sum/K개의 바구니로 나도리들을 모아야 한다. 2. 총 나도리 합 sum이 K의 배수가 아니면 무조건 불가능하다. 3. 최소 횟수로 나도리를 모으려면 이미 나도리가 최대한 많이 들어있는 바구니에 모아야 한다. 1. 총 나도리 합을 sum이라고 하면, sum/K개의 바구니로 나도리들을 모아야 한다. 총 나도리의 수를 sum마리라고 하면, N개에 바구니에 흩어져있는 나도리들을 각 바구니에 K마리씩, 총 sum/K개의 바구니로 모으면 된다. 2. 총 나도리 합 sum이 K의 배수가 아니면 무조건 불가능하다. 남는 나도리 없이 전부 터트려야하므로 당연히 sum이 K의 배수가 아니면 무조건 불가능하다. 3. 최소 횟수로 나도리를 모으려면 이미 나도리가 최대한 많이 들어있.. 2022. 2. 23.
백준 19587번 객실 배치 - C++(cpp) 풀이 1. N층짜리 건물에 객실을 배치하는 방법의 수를 점화식으로 나타낸다. 2. 점화식을 행렬의 곱으로 나타낸다. 3. 분할정복을 이용하여 행렬의 거듭제곱을 계산한다. 1. N층짜리 건물에 객실을 배치하는 방법의 수를 점화식으로 나타낸다. T(n) = N층짜리 건물에 객실을 배치하는 방법의 수 T(n) = A(n) + B(n) + C(n) A(n) = n층은 비워두는 경우의 수 B(n) = n층은 1호실을 채우는 경우의 수 C(n) = n층은 2호실을 채우는 경우의 수 n번째 층의 상태에 따라 n-1번째 층의 상태를 결정하는 경우가 달라진다. n번째 층이 비어있다면: n-1번째 층은 비울수도, 1호실만 채울수도, 2호실만 채울수도 있다. n번째 층의 1호실을 채웠다면: n-1번째 층은 비우거나 2호실만 채울.. 2022. 2. 23.
백준 16637번 괄호 추가하기 - C++(cpp) 풀이 + 그림 설명 1. 앞에서부터 차례로 괄호를 하는 경우와 안 하는 경우를 모두 고려한다. 2. 수식의 끝까지 고려했으면 현재 계산 값을 가지고 최댓값을 갱신한다. 1. 앞에서부터 차례로 괄호를 하는 경우와 안하는 경우를 모두 고려한다. N=19밖에 되지 않으므로 대충 연산자 한 개마다 괄호를 할지 말 지를 결정한다고 쳐도 2^9가지밖에 나오지 않는다. 따라서 완전 탐색으로 풀 수 있다. 앞에서부터 차례로 괄호를 하는 경우와 안하는 경우를 모두 고려해준다. 괄호를 하지 않는 경우 그냥 순차적으로 가장 앞에 있는 두 수를 계산해주면 된다. 반대로 괄호를 하는 경우에는 맨 앞의 두 수를 연산하지 않고, 두번째 수와 세 번째 수를 먼저 계산한 후, 그 결과와 첫 번째 수를 연산해준다. 2. 수식의 끝까지 고려했으면 현재 계산.. 2022. 2. 18.
백준 17298번 오큰수 - C++(cpp) 풀이 + 그림 설명 1. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 2. 스택에는 앞으로 오큰수가 될 수 있는 수들만 들어있게 유지한다. 3. 어떤 수 x를 고려하는 시점에서의 스택 top이 x의 오큰수이다. 1. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 즉 NGE(N), NGE(N-1), ..., NGE(2), NGE(1) 순으로 구할 것이다. 2. 스택에는 앞으로 오큰수가 될 수 있는 수들만 들어있게 유지한다. 스택을 사용한다. 스택에는 앞으로 어떤 수의 오큰수가 될 수 있는 수들만 들어있게 유지해준다. 주어진 수열을 높이가 있는 막대라고 생각해보자. 먼저 가장 오른쪽에 있는 7의 오큰수인 NGE(4)를 구해보자. 스택이 비어있으므로 7의 오큰수는 없다... 2022. 2. 17.
반응형

티스토리툴바