중점 1. 점화식 구하기, 문제에 나와있는 규칙을 이용한 점화식 구하기 2. 계산 양에 비해서 적은 문제 풀이 시간 (1초) 하위 단계의 문제의 풀이 방식 및 정답이 상위 문제의 답에 영향을 미치며 반복되는 같은 방식의 계산이 존재한다. 따라서 DP알고리즘을 사용하여서 문제를 해결하였다. 이때 점화식을 파악하는 것이 중요했다. 계단의 점수를 더하여 total에 저장하여 사용했다. 이때 연속되는 3개의 계단을 모두 사용하지 못하기에 n-1의 계단을 밟는다면 무조건 total[n-3]를 이용하여야 하고 그렇지 않다면 total[n-2]와 n의 계단을 사용해야 한다. 따라서 두가지의 선택지 중 max값을 비교하면 된다. 정답 코드 #include using namespace std; int n; int sta..
coding-test
중점 1. 세개의 수의 합이라는 점 2. 집합안에 속하는 숫자 중에서 최댓값을 찾는 것 2번 중점 때문에 파라메트릭 서치에 대해서 바로 생각해 보았다. 최댓값을 주어진 수 내에서 찾아야 하는 것이기 때문이다. 시간 제한은 1초이기 때문에 더더욱 빨리 찾을 필요가 있었다. 하지만 세수의 합이기 때문에 바로 찾을 수는 없었다. 따라서 입력받은 숫자들을 배열에 입력받고 짝을 지어서 두 수를 더한 값을 vector에 저장했다. 이후 배열과 vector를 모두 정렬 시키고 배열의 가장 마지막 부분에서 0번째 배열 값 부터 빼가며 vector에서 해당 값이 있는지 이분 탐색을 이용했다. 최대값을 찾아야하므로 sort에서 오름차순인 배열에서 n에서 0으로 차례로 빼서 합을 찾았다. 막상 코드를 작성하고 나니 파라메트..
중점 1. 모든 로프에 같은 무게의 하중이 걸린다는 점 2. 최대의 중량을 구해야한다. 로프가 가지는 최대의 중량을 입력받는다. 입력 받은 중량들을 sort한다면 n번째 로프의 최대 중량은 n-1번째 로프의 최대 중량 보다는 무조건 많다. 그렇다면 n-1번째 로프의 최대 중량 * 2가 가질 수 있는 최대 중량일 것 이다. 이러한 원리로 n개 중 몇개의 로프를 이용할 때 가장 최대 인지 비교하며 최대값을 저장하는 그리디 알고리즘을 사용하였다. 정답 코드 #include using namespace std; int n; int w[100005]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i < n; i++) c..
중점 1. 가장 큰 자리의 수는 1로 고정이 되어있다. 2. 1이 연속되는 숫자는 나오지 못한다. 3. 한 자리 숫자는 1개, 두자리 숫자는 1개, 세자리 숫자는 2개, 네자리 숫자는 3개가 나온다. 정확한 원리는 모르지만 n이 커질때 n-1, n-2의 개수를 더한 것이 n의 자리수의 개수가 나온다. 따라서 피보나치 수열이라는 것을 알게 되었고 코드를 짤 수 있었다. 정답 코드 #include using namespace std; long long d[92]; int n; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; d[1] = 1; d[2] = 1; for (int i = 3; i
중점 1. 하위 문제의 반복이 상위 문제의 답에 영향을 미친다. 2. 문제의 풀이과정이 반복적인 과정을 거친다. 3. 각 대각선의 숫자만 더할 수 있다. 4. 항상 큰 숫자만 찾아 가는것이 답임이 확실시되지 않는다. 위의 중점 사항 중 4번을 생각하면 DP 알고리즘을 이용해 합계를 같은 피라미드 구조로 합계를 저장해야 한다고 생각했다. 또한 피라미드 구조를 행렬로 치환하여서 저장하였다. 이후 반복문에서 합계를 저장하며 배열을 채운다. 이때 접근 가능한 곳에서의 max 값을 선택하여서 밑의 행렬에 저장한다. 이후 최댓값을 합계를 저장한 행렬 중 가장 밑의 부분에서 찾아서 출력하면 된다. #include using namespace std; int d[502][502]; int total[502][502];..
중점 1. 가능한 많은 회의가 진행되어야 한다. 2. 회의가 시작하자마자 끝날 수도 있다. 3. 회의를 많이 하기만 하면 된다. 효율적으로 회의를 진행 할 필요가 없다. 먼저 해당 문제를 보았을때 가능한 많은 회의의 진행을 위해서 그리디 알고리즘의 사용을 해야겠다고 생각했다. 또한 시작하자마자 끝날 수 있고 최대의 개수를 파악하기 위해서 입력받은 회의 시간을 끝나는 시간을 기준으로 sort한다면 많은 회의를 선택한다는 생각이 들었다. 하지만 풀리지 않는 문제가 있었는데 만약 2시에 회의가 끝나고 다음 회의가 3-4시, 2-4시인 회의 중 택 1을 해야한다면 자연스럽게 공백의 시간이 있으면 안된다고 생각하여서 2-4의 회의를 선택해야 한다고 생각했다. 따라서 정렬을 먼저 끝나는 시간으로 한 후에 다시 시작..
