본문 바로가기
반응형

Problem Solving/BOJ228

백준 18138번 리유나는 세일러복을 좋아해 - 스위프트(Swift) 풀이 1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다. 2. 티셔츠와 카라를 이분 매칭 한다. 1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다. 티셔츠 집단과 카라 집단을 최대로 매칭 시켜야 하는 이분 매칭 문제이다. 먼저 각 티셔츠와 카라들을 그래프의 정점이라고 생각한 뒤, 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍을 간선으로 연결해 그래프를 만들어준다. 2. 티셔츠와 카라를 이분 매칭 한다. 이제 완성된 그래프에 대해 이분 매칭을 진행하면 된다. DFS를 사용하여 구현하였다. import Foundation var N = 0, M = 0 var Tshirts = Array(repeating: 0, count: 201) var co.. 2022. 3. 8.
백준 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.
반응형

티스토리툴바