1. 문제 25496번: 장신구 명장 임스 첫 번째 줄에 정수 $P$와 정수 $N$이 공백으로 구분되어 주어진다. ($1 \le P \le 200$, $1 \le N \le 1\,000$) 두 번째 줄에는 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 200$) www.acmicpc.net 2. 풀이 욕심쟁이 알고리즘(Greedy Algorithm)을 통해서 풀이할 수 있는 문제로, 남아 있는 피로도를 어떻게 하면 가장 효과적으로 사용할 수 있을 것인가를 해결하는 것이다. 장신구를 제작하는데 드는 피로도가 작은 것을 최대한 먼저 제작한다면, 다른 장신구를 제작할 수 있는 문제로 분할할 수 있다. 따라서 입력받은 피로도를 작은 순서로 정렬하여, 순..

1. 문제 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 2. 풀이 '강산이는 휴가를 P일 중 L일만 사용할 수 있다'라는 것은 전체 V를 P로 나눈 몫에 L을 곱한 것만큼 휴가를 캠핑장을 사용할 수 있다는 말이다. 중요한 것은 V를 P로 나눈 나머지를 곧바로 더해주면 안된다는 점이다. (L < P) 이므로, V % P가 L보다 클 수 있다는 점을 놓치지 않아야 통과할 수 있다. 즉, min(V % P, L) 값을 추가로 더해주면 풀이할 수 있다! 3. 소스코드 더보기 public class Main ..

1. 문제 25513번: 빠른 오름차순 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1, 2, 3, 4, 5, 6중 하나의 수가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c www.acmicpc.net 2. 풀이 전형적인 BFS를 통한 경로탐색 문제이며, 방문해야 하는 노드가 순차적으로 정해져 있는 형태의 문제다. 우선 보드가 5 x 5 로 작은 형태이므로 구현 자체에도 큰 어려움이 없을 것으로 생각된다. 다만, 이미 방문한 노드를 어떻게 다시 방문하지 않을 것인가를 판단하는 것이 중요한데, 대개 이러한 유형의 경우 3차원 배열로 방문배열을 선언하여 현재 탐색중인 idx 에서는 중복된 칸을 ..

1. 문제 12887번: 경로 게임 첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다. www.acmicpc.net 2. 풀이 문제가 다속 복잡해보이기 위해 노력했으나 사실 핵심을 간파하기는 쉬운 유형이다. 격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른쪽 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오. 왼쪽-오른쪽 경로가 항상 존재하는 게임판만 입력으로 주어진다. 이를 다시 정리하자면, 좌측 끝에서 우측 끝으로 가는 경로에서 방문하지 않은 칸의 개수를 최대로 만들라는 말이며, 이는 곧 최소경로를 찾으라는 말과 동일하다. 그렇다면 우리는 아래의 과정을 통해서 본 문제를 풀 수 있게 된다. 입력과 동..

1. 문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 입력으로 제공된 카드들의 누적합을 최소로 만드는 경우의 수를 만들라는 문제다. 이는 Greedy로 접근이 가능한데 이유는 아래와 같다. a, b, c, d 총 네 개의 카드 묶음(a < b < c < d)이 있다고 가정해보자. 이 때, 먼저 만든 묶음은 또 다른 카드 묶음과 합쳐져야 하므로 한 번 더 더해져야 함을 의미한다. 즉, 더 큰 카드 묶음을 이용하여 새로운 묶음을 만들수록 큰 수가 중복해서 더해진다는 것을 의미한다. ..

1. 문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 크게 어려울 것이 없는 단순 구현문제다. 아래 풀이한 코드를 보면 충분히 흐름을 이해할 수 있을 것으로 생각된다. 다만, 해당 문제에서 가장 중요한 조건이 하나 있는데, 미세먼지 확산에 대한 것이다. 바로 미세먼지는 모든 칸에서 동시에 확산된다는 점인데, 이는 다시 말해 단순 반복문을 통해서 확산된 미세먼지가 동일한 쿼리 내에서 상호 영향을 주면 안된다는 얘기가 된다. 즉, 각 기준점의 확산량을 누적할 수 있는 별도의 배열을 선언해야 한다는..

0. 복습 다형성은 지연 바인딩(lazy binding) 매커니즘을 통해 구현된다 지연 바인딩: 메시지에 응답하기 위해 실행될 메서드가 컴파일 타임이 아닌 런타임에 결정되는 것 상속은 코드 재사용에 있어 가장 널리 알려진 방법이지만, 캡슐화의 측면에서 합성이 더 좋은 방법이다 유연한 객체지향 프로그램을 위해서는 컴파일 타임 의존성과 런타임 의존성이 달라야 한다 1. 들어가며 객체지향의 본질은 협력하는 객체들의 공동체를 창조하는 것으로, 객체지향 설계의 핵심은 협력을 구성하기 위해 적절한 객체를 찾고 적절한 책임을 할당하는 과정에서 드러난다. 기능을 구현하기 위해 어떤 협력이 필요하고 협력을 위해 어떤 역할과 책임이 필요한지를 고민하지 않은 채 이른 시기에 구현에 초점을 맞추는 것은 변경하기 어렵고 유연하..

1. 문제 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이 N과 M 시리즈의 마지막 문제다. 문제의 핵심 조건은 아래와 같다. 수열에서 같은 수를 여러번 사용할 수 있음 비내림차순으로 출력해야 함 비내림차순 자체는 입력받은 수열을 오름차순으로 정렬하면 되서 어렵지 않은 조건이지만, 같은 수를 여러번 사용할 수 있게는 어떻게 처리할 것인가? 바로 입력 받은 수열의 중복을 제거하는 것이다! 수열의 중복을 제거하고 단순하게 수열의 요소들을 반복 선택하여 M의 길이로 맞춰주면 되는 것으로 코드를 보면 보..

01. 영화 예매 시스템 영화 예매 시스템을 구현하면서 객체지향 프로그래밍에 대한 개념을 잡아본다. 1) 요구사항 정의 영화: 영화에 관련된 기본 정보(제목, 상영시간, 가격정보, ...) 상영: 실제로 관객들이 영화를 관람하는 사건 할인조건: 가격의 할인 여부(순서조건, 기간조건), 할인 정책에는 다수의 할인 조건을 설정할 수 있음 순서조건: 상영 순번을 이용해 할인 여부를 결정 기간조건: 영화 상영 시작 시간을 이용해 할인 여부를 결정 할인정책: 할인 요금을 결정, 영화당 하나의 할인 정책만 할당할 수 있음 금액 할인 정책: 예매 요금에서 일정 금액을 할인해주는 방식 비율 할인 정책: 정가에서 일정 비율의 요금을 할인해주는 방식 02. 객체지향 프로그래밍을 향해 진정한 객체지향 프로그래밍으로의 전환은..

1. 문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 2차원 DP형태의 문제라 직관적으로 해답을 떠올리기 다소 어려운 유형의 문제라고 할 수 있다. 따라서 점화식을 먼저 한 번 도출해보도록 하자. 숫자 N을 정수 K개의 조합으로 만들 수 있는 문제를 다시 재조합하면 아래와 같이 생각할 수도 있다. dp[N][K]는 N을 K개 조합으로 만드는 경우의 수를 의미하고, 예시로 N = 6이고 K = 4라고 가정해보자. (_ , _ , _ , L) 네 개의 숫자 조합에서 마지막 자리를 L(0 ≤ L ≤ 6) 로 결정한다면, L 값에 따라서 아래 표의 경우의 수가 만들어짐을 알 수 있다. L case 0 dp[6][3] 1 dp[..