https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 점화식을 구하는 데 어려움을 겪었는데, 노가다로 N=3까지 계산했으나 규칙이 눈에 들어오지 않았다. 검색을 통해 점화식을 보고서야 이런 규칙이었구나 깨닫게 되었다. 현재 dp는 (한 단계 전 dp의 두 배 + 두 단계 전 dp)%9901 이다. 또다른 방법으로 3×N 행렬을 만들어 현재 우리가 빈 우리일 경우, 왼쪽에 사자가 있는 우리일 경우, 오른쪽에 사자가 있는 우리일 경우로 나누어 생각해보았다. 빈 우리일 경우, 이전 우리가 빈 우리든, 사자가 어디 있든 상관 없이 세 경우를 모두 ..
https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 💡IDEA 그리디 알고리즘, 정렬을 사용하는 문제이다. 정렬은 key=lambda를 사용하여 배열의 0번째 값인 서류심사 성적으로 먼저 내림차순 한 후 1번째 값인 면접심사 성적으로 내림차순 했다. 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발하기 위해 먼저 서류심사 성적으로 내림차순 정렬 후 첫번째 ..
https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 💡IDEA 수학의 소수를 사용하는 문제이다. 2022.07.21 - [Algorithm/BOJ] - [BOJ][python] 6588. 골드바흐의 추측 [BOJ][python] 6588. 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 이분 탐색이란 가장 작은 값과 가장 큰 값을 기준으로 가운데 값을 찾아 타겟값을 비교하여 좌우 변수를 조정하며 탐색하는 방법이다. 이 문제에서는 가운데 값보다 큰 높이의 나무를 잘라낸 합으로 비교하며 좌우 변수를 좁힌다. 절단기에 설정할 수 있는 최대 높이를 구하기 위해 구한 합과 타겟값을 비교하며 가장 큰 높이를 ..
https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 💡IDEA 수학을 사용하는 문제이다. 문제는 크게 어렵지 않지만 시간초과의 늪에 빠지기 쉬운 문제이다. 소수를 구해두는 건 while문 안에 넣으면 시간이 오래 걸리므로 먼저 계산해두어야 한다. 구해둔 이 소수배열을 앞에서부터 확인하는데, 더해서 n이 되는 소수를 구해야 하므로 i번째가 소수인 것과 n-i번째가 소수인 것을 확인해주면 된다. 발견할 시엔 출력 양식에 맞추어서..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 1을 k번 더한 수를 합해서 점점 줄여가며 개수를 구하는 것은 알았으나, 점화식을 어떻게 써야할 지가 어려웠다. 입력받은 coins에서 동전의 가치 i를 사용하여 dp를 구성해야 하는데, i~k 사이의 수 j번째 값은 j 값 + (j-i) 값을 구할 수 있다. 쉽게 말하자면, i 값을 가진 동전을 사용하는 경우와, 사용하지 않는 경우를 더해서 계산한다고 생..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡IDEA 수학, 브루트포스를 사용하는 문제이다. 주어지는 L, C가 15 이하인 수이기 때문에, 브루트포스로 해결할 수 있을 것 같았다. 바로 itertools의 combinations 함수, 즉 조합 함수를 사용하여 C개의 문자 중 L개를 선택한 조합들을 찾는다. 이 암호들 중 자음이 두개 이상, 모음이 하나 이상인 암호만 출력하도록 한다. 📌CODE import sys from itertools ..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 먼저 모눈종이의 사각형을 표시하기 위해 2차원 배열에 입력받은 사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표를 사용하여 사각형이 존재하는 부분은 1로, 그렇지 않은 부분은 0인 상태로 둔다. 모든 사각형을 표시했다면, 사각형이 없는(0) 지점을 찾아서 BFS를 수행하며 상하좌우로 연결된 영역의 넓이를 세며 방문 확인을 해준다. BFS를 수행한..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 규칙을 찾기 위해 N이 1, 2, 3인 경우를 생각해보자. 먼저 N=1인 경우, 오르막 수는 0~9까지 각 1개씩 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]으로 모두 10개이다. N=2인 경우, 오르막 수는 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]으로 모두 55개이다. N=3인 경우, 오르막..
https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 💡IDEA 수학을 사용하여 푸는 문제이다. 소수인 수를 구하기 위해 에라토스테네스의 체 방법을 이용했다. 이는 소수인 2부터 시작한다. 2의 배수인 값을 모두 소수가 아님을 체크하고, 체크되지 않은 값 중 가장 작은 3은 소수로 여긴다. 이후 3의 배수를 모두 체크하는 식으로 반복된다. 이런 방법을 사용하여 2*n까지의 소수를 모두 구하고, 그 중 n과 2*n 사이의 소수의 개수를 센다. ..
