https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net dp 문제다. 완전 순열로 본인이 본인 것을 선택하는 경우를 제외한 순열이다. n = 2인 경우 a - 2, b - 1 이렇게 한 가지 경우다. n = 3인 경우 a - 2, b - 3, c - 1 a - 3, b - 1, c - 2 이렇게 두 가지 경우다. n = 4인 경우 a - 2, b - 3, c - 4, d - 1 a - 2, b - 4, c - 1, d - 3 a - 2, b - 1, c - 4, d - 3 a - 3, b - 1, c - 4, d - 2 a - 3, b - 4, c - 1, d - 2..
Algorithm
https://www.acmicpc.net/problem/7983 7983번: 내일 할거야 내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다. www.acmicpc.net 그리디 문제다. 과제를 최대한 미뤄 내일부터 연속으로 최대 며칠 놀 수 있는지 구하는 문제다. 최대한 뒤로 미뤄야하기 때문에 맨 뒤에서부터 채워나갔다. 우선 마감일을 기준으로 정렬을 했다. 내림차순으로 데이터가 필요하지만 오름차순으로 정렬하고 뒤에서부터 접근했다. 마지막 마감일을 기준으로 걸리는 일수를 빼주고 그 후로는 이전 과제 시작일과 해당 과제 마감일 중 작은 값을 해당 과제의 마감일로 계산했다. 최종적으로 마감일이 가장 빠른 과제..
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net dp문제다. 아이들을 옮기는데 다른 제한이 없으므로 이미 일부분 정렬되어 있는 아이들을 제외하고 움직이는 방법이 최선이다. 증가하는 가장 긴 부분수열을 구하고 전체 수열의 개수에서 부분 수열의 개수를 빼주면 된다. 배열을 순회하면서 해당 숫자를 기준으로 앞 쪽을 탐색한다. 앞 부분 숫자 중 해당 숫자보다 작은 숫자가 있다면 현재 dp배열의 값과 비교한다. if (arr[i] > arr[j]) dp[i] ..
https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net BFS 문제다. DFS도 가능할 것이라고 생각하나 BFS로 접근했다. 구현 요소도 포함된 것 같다. 재방문이 필요하다는 점에서 고민 요소가 있었다. 조건 없이 계속 재방문 하면 무한 루프가 돌거나 돌지 않아도 메모리가 터질 것이다. 무한 루프를 막기 위해 방문 시 들고 있던 돈을 기준으로 재방문 여부를 결정했다. 방에 들어와서 소지하게 된 돈이 이전에 방문했을 때의 돈을 비교해서 ..
https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 구현 문제다. 문제 그대로 구현하면 되는 문제라 특별히 설명할 부분은 없다. 문제에서 특이한 점이 있다면 왼쪽 위쪽 테두리의 성장 값을 줄 때 각각의 값을 주는 게 아니라 각각의 수가 연속된 개수를 준다는 점이었따. 이 부분을 어떻게 해결할 까 하다가 바로바로 값에 넣어주려 했는데 반복문은 한 번 덜 돌지라도 코드 자체가 너무 비효율적이라 일차원 배열을 생성했다. 처참하게..
https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 투 포인터 문제다. 중복이 없는 수열의 시작과 끝 + 1을 투 포인터로 찾으려고 했다. 1 2 3 4 1 2 의 경우 start = 0, end = 4까지 연산을 거치고 이 때 1 / 1, 2 / 1, 2, 3 / 1, 2, 3, 4의 4가지 수열이 나온다. 2, 3 / 2, 3, 4 / 3, 4 등도 존재하지만 중복 계산을 방지하기 위해 start의 값을 포함하는 수열만을 계산했다. 방법은 금방 찾아냈..
