3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 요약 장애물의 위치가 주어지고, 해당 장애물을 통과하는 최솟값과 그러한 구간의 수를 출력하라 2. 접근 방법 위와 같은 장애물이 있다고 했을 때, 아래서부터 장애물을 통과하는 수를 세어보면 3, 3, 2, 3 입니다. 이런 식으로 완전탐색으로도 충분히 정답은 구할 수 있습니다만, 시간과 메모리가 한정되어 있기 때문에 다른 방법으로 풀어야 합니다. 이모스법 알고리즘을 알고 있다면 쉽게 풀 수 있습니다. 위 그림과 같이 장애물이 시작되는 위치에 +1, 끝나는..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 N x N의 표가 주어지고 좌표가 주어지면, 그 구간의 합계를 구하는 문제이다. 2. 접근 방법 다이내믹 프로그래밍을 이용하여 각각의 구간별 합을 미리 구해놓는다. (DP 테이블) 예를 들어, DP 테이블의 (2,2)의 위치는 기존테이블의 (2,2) + DP(2,1) + DP(1,2) - DP(1,1)이다 즉, 원하는 위치의 수 + DP테이블의 위 + 좌 - 겹치는 구간이다 DP테이블은 (N+1) x (N+1)로 생성하면 편리하다..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 블록들의 높이가 주어지고 블록들 사이에 고일 수 있는 빗물의 양을 구하는 문제입니다. 2. 파이썬 2 - 1. 접근 방법 백준 - 2304 창고 다각형 [구현] 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내 e-room.tistory.com 이전에 풀었던 문제와 거의..
2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 1. 문제 요약 주어진 좌표와 높이에 맞는 다각형의 넓이를 구하라(단, 오목하게 들어가는 부분은 없어야 한다.) 2. 파이썬 조금 비효율적인 방식으로 처음에 풀었습니다 ...ㅎ 2 - 1. 접근 방법 주어진 좌표와 높이에서 가장 큰 부분에 맞는 이중배열을 생성 현재 높이와 이전의 높이 중 가장 높은 높이로 이중배열을 채워준다 동일한 방식으로 좌표 역순으로 진행 생성된 두 이중배열을 비교하여 둘 다 채워진 경우 넓이를 증가 시킨다 2 - 2. 코드..
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 간단 요약 해당 문제는 수열이 주어지면, 해당 수열의 부분연속수열의 합중 가장 큰 값을 구하는 문제이다. 2. 접근 방법 순차적으로 값을 더한다. 다음에 올 숫자가 이득인지 손해인지를 판단한다. 현재까지의 값 + 수열의 현재 인덱스의 값 vs 수열의 현재 인덱스의 값을 비교하여 더 큰 값을 취한다. 예를 들어 아래와 같은 수가 주어질 경우 -4는 음수이지만 10과 합하면 6이다. 해당 값과 3을 더하면 9이므로, 3보다 크기때문에 손해가 아니므로 취한다. 아래처럼 2..
14252번: 공약수열 서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘 www.acmicpc.net 간단 요약 해당 문제는 배열 A가 주어지면 해당 배열을 오름차순 정렬하여, 인접한 수들의 최대공약수가 1이 되도록 숫자를 추가하고, 몇 개가 추가돼야 하는지 그 개수를 리턴하면 됩니다. 접근 방법 추가될 숫자를 찾는 것이 아닌, 추가될 숫자의 개수만 구하면 됩니다. 문제의 핵심은 모든 수는 인접한 수를 최대공약수 1로 만들려면 1개 또는 2개로 해결이 됩니다. 해당 문제는 이 개념을 아느냐 모르느냐로 난이도가 결정되는 듯한데, 증명하는 방법은 잘 모르겠습니다. ..
2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 해당 문제는 최대공약수와 최소공배수가 주어지면, 주어진 최대공약수와 최소공배수를 만족시키는 두 수 A, B 중 A + B가 가장 작은 경우를 찾는 문제입니다. 접근 전략 A X B 는 최대공약수 X 최소공배수 와 같습니다. 완전탐색으로 가능한 모든 경우의 수를 찾는다. 최대공약수의 배수들을 탐색한다. 최대공약수의 배수들 중 A X B 와 나누어 떨어지는 경우를 찾는다. 주어진 최대공약수와 탐색하는 수의 최대공약수가 같은 경우를 찾는다. (유클리드 호제법으로 최대..
1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 해당 문제는 주어진 숫자가 소수인지 판별하는 문제입니다. 낮은 난이도이기에 어떠한 방식으로 풀어도 통과가 됩니다. 대표적인 3가지 방법으로 풀어보겠습니다. 1. 일반적인 방법 가장 일반적인 방법으론 2부터 1씩 늘려가며 해당 숫자가 나누어 떨어지는지 보는 방법입니다. // Java static boolean isPrime(int number) { if (number
15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net 해당 문제는 제곱수를 구하는 문제입니다. 이 사실을 알면 굉장히 쉽게 풀 수 있습니다. 다만, 저는 몰랐구요 ㅎ... 정답을 찾아놓고 최적화 하는 것을 좋아해서 맨 처음에 그냥 완전탐색으로 for문 두 번 돌렸습니다. 작은 숫자들은 무난하게 되더군요. 다만 제출했더니 바로 메모리가 터집니다 ㅎㅎ.. 사실 예상했던 부분인지라 좀 더 살펴보았습니다. 보다보니 규칙이 보이더군요. 3, 5, 7, 9, 11 ~ 이런 식으로 숫자가 2씩 증가하면서 백기의 숫자가..
