문제 이해 단계 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 행렬 N개를 곱하는데 곱하는 순서에 따라 값이 달라진다. 행렬 N의 크기가 주어졌을 때, 곱셈 연산 횟수의 최솟값을 구하는 문제곱셈 연산을 하는 방법은 크기가 NxM인 행렬 A와 MxK인 행렬 B가 있을 때, AxB = N x M x K를 크기로 계산한 후 행렬은 N x K가 된다. 입력은 무조건 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다. 문제 접근 단계 ..

문제 이해 단계 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2차원 좌표 평면 위의 2개의 선분 L1과 L2가 주어진다. 두 선분이 교차하는지 아닌지를 판단하는 문제. 교차하면 1, 그렇지 않으면 0을 출력한다. 입력으로 L1의 양 끝 좌표(x1, y1) (x2, y2) L2의 양 끝 좌표 (x3, y3) (x4, y4)가 들어온다. 문제 접근 단계 문제 조건에서 시간제한이 0.25초로 상당히 짧은 것을 볼 수 있다. 그리고 두 좌표를 연결하는 선분 L1, L2이기 때문에 일차함수라는 것을 알 수 있..

문제 이해 단계 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 접근 단계 1번부터 ~N번까지 N명의 학생들을 키 순서대로 줄을 세운다. 입력을 키를 비교한 두 학생의 번호 A, B가 M개 들어온다. 이는 A학생 뒤에 B학생이 서야 한다는 의미이다. 학생들을 앞에서부터 줄을 세운 결과를 출력하는데, 답이 여러 가지인 경우에는 아무거나 하나 골라서 출력한다. 문제 구현 단계 일단 제한사항부터 살펴보..

문제 이해 단계 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 정수로 되어있는 용액이 N개가 주어진다. 이 중에서 3개를 골라 3개의 합이 0에 가장 가까운 경우를 만들 때, 그때의 세 용액을 찾아서 오름차순으로 출력하는 것이 문제이다. 문제 접근 단계 문제는 상당히 간단한데, 일단 수의 범위랑 제한사항부터 살펴보자. 산성 용액과 알칼리 용액으로 구분해 놨지만, 사실상 용액의 범위는 -1,000,000,000 ~ 1,00..

문제 이해 단계 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net N개의 건물이 있고, 각 건물마다 먼저 지어져야 하는 건설 순서가 K개 존재한다. 목표로 지어야 할 건물이 있을 때, 해당 건물을 짓는데 걸리는 최소 시간을 알아내는 문제 문제 접근 단계 일단 제한사항부터 살펴보자. 테스트 케이스 T의 개수는 명시되어있지 않다. 그리고 건물의 개수 N은 최대 1,000개 건설 순서 K의 개수와 최대 시간 소요시간은 100,000까지이다. 여기..

문제 이해 단계 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net N x 3 짜리 맵이 존재한다. 각 칸에는 0 ~ 9 숫자가 적혀있다. 가장 윗 칸에서 한 칸씩 내려오는데, 내려올 수 있는 방향은 바로 아래 또는 대각 방향밖에 없다. 가장 위에서 아래로 이동할 때, 얻을 수 있는 최대 점수와 최수를 구하는 문제 문제 접근 단계 예제 입력을 통해 한번 유형을 찾아보려고 해 보자. 만약 내가 마지막 층(N)행의 2번째 칸인 9를 선택했다고 해보자. 이 입력에서 ..

문제 이해 단계 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net n개의 도시와 m개의 버스가 존재한다. 버스는 A도시에서 출발하여 B도시에 도착하는 정보로 주어진다. 그리고 각 버스마다 드는 비용이 존재한다. 또한 입력으로 출발지와 도착지가 주어질 때, 출발지에서 도착지까지 가는데 드는 최소 비용과 경로를 출력하는 것 문제 접근 단계 일단 문제 조건부터 살펴보자. 도시의 개수 n은 최대 1,000 간선의 개수(버..

문제 이해 단계 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net N = 24 일 때의 출력이다. 예제를 보고 규칙을 유추하고 별을 찍는 문제 입력 N은 무조건 3 * 2^k로 들어온다. 여기서 k의 범위는 0≤k≤10이다. 문제 접근 단계 별 찍기 시리즈 문제이다. 때문에 구현문제인 것 같은데, 어떤 식으로 구현해야 할까? k의 범위가 0부터 10까지니까 순서대로 해봤다. 이 이상은 그림이 너무 커질 것 같아서 k = 2 일 때까지만 그려보도록 하겠다. 이렇게 k가 1씩 커져갈 때의 규칙을 보면 ..