https://www.acmicpc.net/problem/2253 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 1. Logic 1번째 돌에서 시작하여 n번째 돌까지 가야하지만 중간에 밟지 못하는 돌이 존재한다. 이런 돌을 걸러주기 위해 bool배열을 통해 체크해준다. 재귀를 통해 0까지 들어가며 부문문제를 해결해준다. 부분문제는 1. 이전에 이동했던 칸수와 동일하게 이동하는 경우 2. 이전에 이동했던 칸수-1칸 이동하는 경우 3. 이전에 이동했던 칸수+1 이동하는 경우 이렇게 3가지 이다..
백준
https://www.acmicpc.net/problem/11653 1. Code #include using namespace std; int main() { int n; cin >> n; if (n == 1) return 0; for (int i = 2; i
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. Logic 이 문제의 부분문제는 총 3가지로 나눌 수 있다. 1. 사자를 배치하지 않는 경우(항상) 2. 사자를 오른쪽에 배치하는 경우(이전에 사자를 왼쪽에 배치했을 때) 3. 사자를 왼쪽에 놓는경우 (이전에 사자를 오른쪽에 배치했을때) 이렇게 3가지 경우를 끊어서 해결해주면 된다. 아래 코드를 보면 이해가 될 것이다. 2. Code #include #include using namespace std; int n; int dp[100001][3]; int solve(int idx, int prev) { if(idx == n)..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1. Logic dp배열이 의미하는 것은 배열에 해당하는 카드를 구매할때의 최댓값이다. dp[구매하는 카드 갯수] = 최댓값. 최댓값을 구하는 방법은 1개짜리 팩 + 카드 3개를 구매하는데 필요한 최댓값 2개짜리 팩 + 카드 2개를 구매하는데 필요한 최댓값 3개짜리 팩 + 카드 1개를 구매하는데 필요한 최댓값 4개짜리 팩 이렇게 경우의 수를 나눠볼 수 있다. 2. Code #include #include..
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. Logic 우리는 가장 큰 정사각형의 크기를 구해야 한다. 그렇기 때문에 dp배열의 의미는 가장 큰 정사각형의 한변의 길이를 의미한다. 한 지점을 기준으로 정사각형이 되기위해 쪼개지는 부분문제는 총 3가지가 있다. 아래 대각선 오른쪽 이렇게 3방향으로 쪼개진다. 이 3개의 부분문제의 리턴값의 최솟값이 현재 위치에서의 최댓값이 된다. 2. Code #include #include #include using namespace std; int n, m; string ..
https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 1. Logic 두개의 수를 먼저 골라 합을 만들어 놓고 나머지 한개의 수를 골라 0이 되는 수를 카운트 하면 된다. 이 문제에서는 중복되는 수가 나올 수도 있기 때문에 원하는 수가 먼저 나오는 index(lower bound) 원하는 수가 나오는 가장 마지막 index(upper bound) 두개를 구해 빼주어 갯수만큼 구해줬다. 밑의 코드에서 tempSum에 -를 붙혀준 이유는 우리는 a+b+c=0..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1. Logic 전체 인원의 반을 나눠서 팀을 구성하기 때문에 기저조건을 N/2로 설정한 후 DFS를 진행한다. N/2까지 갔을 때 전체인원의 반은 check배열에 true로 표시되어있고 반은 false로 표시되어 있을 것이다. true로 선택된 번호는 스타트 팀에 배정을 하고 false인 인원은 링크 팀에 배정을 하여 DFS를 돌며 최소값을 구한다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. Logic 부분문제를 3가지로 나눌 수 있다. 포도주를 안마시는 경우 포도주를 1잔 연속해서 마시느 경우 포도주를 2잔 연속해서 마시는 경우 그래서 DP테이블을 정할 때 DP[현재 인덱스][선택 여부] 로 정의했다. 선택 여부 별 의미하는 바는 > 0:이전에 포도주 안마심, 1:이전에 한잔만 마심, 2:이전에 두잔 연속해서 마심 입력으로 받은 첫번째 수에서 선택할지 말지여부를 처리하는 것은, ..
https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 1. Logic 비트필드를 사용하여 현재 위치에서 블럭을 놓은 후 생기는 모양에 대해서 처리해줬다. 그림으로 보면 이 모양(1 | (1
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1. Logic 단순 다익스트라에 간단한 후처리를 요구하는 문제이다. 다익스트라로 첫 해킹을 당한 컴퓨터부터 시작해서 감염을 시키고 다익스트라 이후 dist배열 전체를 순회하여 INF가 아닌 배열들의 갯수를 세주면 감염되는 컴퓨터 수를 구할 수 있고 걸리는 시간은 전체 배열을 순회하며 가장 큰 배열의 값을 구하면 된다. 2. Code #include using namespace std; const i..
