https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 이 문제는 배낭을 활용해서 해결할 수 있다. 배낭은 호텔에서 수용가능한 인원의 크기 만큼 담아야 한다. 호텔에서 수용가능한 인원의 크기는 최대 인원 수 * 최대 홍보 비용 이다. 왜냐하면 N개의 도시에 대해 최소 비용인 C원 만큼 고객을 만들어야하기 때문이다. DP[i] = 돈을 i원 만큼 사용했을 때 최대 확보 고객이라고 한다면 C는 최대 1000이며, 도시를 홍보할 때 드는 비용은 최대 1..
분류 전체보기
https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 이 문제는 DP를 사용해 해결할 수 있다. 문제를 보면 X 지점에서 돌을 건널 수 있는 경우의 수는 3가지이다. X - 3 X - 2 X - 1 X X+1 1. X-3 지점에서 엄청 큰 점프로 X로 이동 2. X-2 지점에서 큰 점프로 X로 이동 3. X-1 지점에서 작은 점프로 X로 이동 위 경우의 수가 일치하는 지점은 4번째 돌까지 이동했을 경우에 해당하기 때문에 이전의 이동 할 수 있는 경우의 수는 아래와 같다. 1. 작은 점프로 이동할 수 있는 경우 2. 큰 점프로 이동할 수 있는 경우 3. 작은 점프 2번으로 이동..
https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 www.acmicpc.net 이 문제는 dynamic programming 기법을 사용해 해결할 수 있다. 문제에서 주어지는 징검다리는 1번돌 부터 N번째 돌까지 건너갈 수 있는 여부를 확인한다. 그 다음 건너갈 수 있다면 dp 배열에 true를 넣는다. i번째 dp 배열의 요소가 false인 경우에는 건너갈 수 없는 경우이기 때문에 무시하고, true인 경우에만 건너..
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 dynamic programming 문제이다. dp에 상담 금액의 최대 값을 저장한다. 이때 상담 시간을 결정하면 일정 기간동안 다음 상담을 신청할 수 없다는 조건이 있기 때문에 현재 결정한 상담 시 금액과 지난 상담의 합과 dp에 저장된 현재 결정한 상담 시간과의 최대 값을 골라 dp에 저장해야한다. #include using namespace std; ..
https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 이 문제는 누적합을 구하여 해결하는 문제이다. 이문제는 11660번과 동일한 알고리즘을 사용하면 된다. https://hanseongbugi2study.tistory.com/67 [Silver 1] 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ..
https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 이 문제는 T를 통해 S를 만들 수 있는지 확인하는 문제이다. 입력으로 S와 T가 들어온다면, S와 T가 같은지 확인인다. 만약 다르다면 문자열의 길이가 다르다면 A와 B를 붙일 수 없으므로 제귀를 멈춘다. 만약 T의 끝이 A인 경우 temp 변수에 T를 담고 A를 제거하고 다시 문자를 붙일 준비를 한다. 만약 T의 앞이 B인 경우 temp 변수에 T를 담..
https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 이 문제는 조합을 이용한 완전 탐색 문제이다. 팀은 2개로 이루어져 있고, 팀의 최소 인원은 2명이다. 따라서 2명의 묶음이 만들어 졌을 때 팀원의 능력치를 더한 후 2개의 팀간의 능력치 차이의 절대 값을 구하면 된다. 팀 간의 묶음은 다음과 같다. 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 ..
https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 이 문제는 완전 탐색으로 오목을 구현하는 문제이다. 오목은 가로, 세로, 좌 대각, 우 대각으로 만들 수 있다. 또한 문제에서 오목이 만들어 졌을 때 가장 왼쪽의 인덱스를 출력해야한다. 문제의 특성을 생각해 봤을 때 한쪽 방향으로만 검사하면 된다는 것을 알 수 있다. 즉, 반드시 가장 왼쪽의 인덱스를 출력해야 한다는 것은 왼쪽으로만 검사하면 된다는 의미이다. 그러면 가로 검사, 대각 검사도 왼쪽으..
