본문 바로가기
728x90

알고리즘339

[python] 백준 2527 직사각형 https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사 www.acmicpc.net 문제 해결 조건을 잘 분리해서 출력하는 문제 우선 겹치지 않는 경우부터 잡는 것이 좋다. 두 직사각형 각각의 x, y의 최소 값 좌표와 최댓 값 좌표가 있는데 어떤 직사각형의 최솟값 좌표가 다른 직사각형의 최댓값 좌표보다 큰 것이 존재하면 겹칠 수 없다.(x, y 둘 중 하나라도) 만약 어떤 직사각형의 최솟값 좌표가 다른 직사각형 최댓값 좌표와 같은 것이 존재한다면 겹쳐서 선이나 점이 만들어진다... 2024. 2. 15.
[python] 백준 27172 수 나누기 게임 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 문제 해결 단순히 두개씩 비교를 하면 시간복잡도가 $O(N^{2})$이 나온다. 이러면 시간안에 통과를 못하는데 이를 보완하기 위해 에라토스테네스 체를 이용하려 한다. 주어진 플레이어가 가진 수들을 리스트 안에 넣고, 그 중 최대치를 maxNum 변수에 저장한다. 각 플레이어가 가진 수들의 배수를 확인해가며 플레이어가 가진 수들 중 있는지 확인을 해가며 점수를 수정한다. CODE import sys fr.. 2024. 2. 14.
[python] 백준 2092 집합의 개수 https://www.acmicpc.net/problem/2092 2092번: 집합의 개수 1부터 T까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1 ≤ S ≤ K ≤ B ≤ A로 한다. 즉, 두 정수 S, B를 입력받아서 www.acmicpc.net 문제 해결 각 숫자의 개수를 알 수 있도록 numbers[num]을 통해 개수를 저장한다. dp[i][j] 를 i까지 숫자중 j개 사용했을 때 가지수를 나타내는 dp함수를 만든다 기본적으로 숫자 i가 k개 있을 때 k개이하를 쓸 수 있으므로 dp[i][j] += 1씩 해준다. (j=k 일때 dp[i][j] += dp[i-1][j-k]이다. 숫자를 1000000으로 나눠.. 2024. 2. 9.
[python] 백준 1943 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 문제 해결 먼저 돈의 총 합을 보았을 때 홀수이면 나눌 수 없다는 것을 알 수 있다. 짝수여도 무조건 가능한 것은 아니지만 총합의 절반을 나눌 수 있다. 절반을 가지고 가지고 있는 동전을 조합하여 맞출 수 있는가?를 보면 된다. 이는 DP를 가지고 풀 수 있다. 처음에는 이론상 0원만 가능하고 동전의 종류별로 채워나가며 dp[total]이 True가 된다면 만들 수 있는 것이다. 만.. 2024. 2. 7.
728x90