백준 2240 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 전 나의 생각 자두가 정해진 이동 횟수에 따라 자두나무에서 얻을 수 있는 최대 자두 개수를 구하는 문제다. 자두가 1초 안에 움직일 수 있기 때문에 1초마다 자두가 떨어지는 나무가 테스트 케이스로 주어진다. 그럼 자두가 어느시간에 도착했을 때 얻을 수 있는 최대의 자두 개수를 구해야 한다. 그럼 자두가 30번의 횟수 안에 어떤 나무 앞에 있으면서 몇초 때 최대값을 얻을 수 있는지 알아야..
알고리즘 및 자료구조/DP
백준 15486 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 풀이 전 나의 생각 본래 퇴사1 문제는 경우의 수가 적어서 DFS로 풀이가 가능했다. 하지만 퇴사2에서는 무려 N이 1500001까지 가능하기 때문에 무조건 DP로 풀어야한다. 이 문제의 포인트는 특정 날짜까지 최대 얼마를 벌 수 있는지 처음부터 탐색하는 것이다. 문제에서 나온 첫 예시를 기준으로 진행하면 1일까지 버는 돈이 없으니 0원 2일까지 버는..
백준 9461https://www.acmicpc.net/problem/9461 9461번: 파도반 수열오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net풀이 전 나의 생각삼각형이 n번째에 어떤 삼각형이 더해져서 값이 나오는지 규칙을 먼저 찾아야 한다. 앞서 말하자면 뭔가 쭉 나열해놓고 규칙을 찾아서 풀었는데 다른 사람들과 점화식이 달랐다. N번째 삼각형이 만들어지기 위해선 N번째 삼각형의 변을 이루고 있는 두 삼각형 변의 길이를 더해줘야 한다고 생각했다. 그래서 되는데로 규칙을 적어봤다. 초반에 나오는 1, 1, 1은 초기값으로 생각하고 적어..
백준 12852 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 전 나의 생각 어느 연산 과정을 통해 최솟값을 구해야 하는 문제들은 대부분 역추적을 이용하면 한층 더 쉽게 접근 할 수있다. 문제의 연산 조건을 보면 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 여기서 알 수 있는건 지정한 수의 연산과정 최대값 즉, 최악의 값은 계속 1을 빼주는 것이다. 그렇기 때문에 DP의 초기값을 모두 자신의 값으로 넣어준다. ex) dp[1] = 1, dp[2] = 2, dp[3] = ..
백준 2579 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 전 나의 생각 일정 조건에 의하여 계단을 올랐을 때 최대로 나올 수 있는 점수를 얻어야 하는 문제다. 조건 1. 한 번에 한 계단, 두 계단 씩 오를 수 있다. 2. 연속해서 3개의 계단을 밟을 수 없다. 3. 마지막 도착 계단은 반드시 밟아야 한다. 이 조건을 의식하면서 처음부터 DP(최대값)를 구해 나가면 생각보다 쉽게 점화식을 구할 수 있다. 문제의 예시인 (10, 20, 15, 25..
백준 11659 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 전 나의 생각 주어진 N의 범위를 보면 100000개 까지 주어질 수 있다. 이 조건의 의미는 2차원 배열과 2중 for문은 사용이 불가능하다는 것이다. 그럼 1차원 배열로 for문 하나만 써서 해결하면 쉽게 풀릴 수 있는 문제라고 힌트를 준 것이다. 문제의 풀이를 생각해보면 구간의 합을 구해야 한다. 그러면 각 상황마다의 구간 합을 모두 구해주고 이를..
백준 12865 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 전 나의 생각 DP를 풀 때 생각해야 하는 두 가지 1. for문을 이용한 DP는 이전 값에 접근해야 되기 때문에 초기값을 0으로 설정해줘야 한다. 2. 어느 분기에 도착했을 때 이전에 구해 놓은 최대 값을 탐색해야 한다. 배낭의 들어갈 수 있는 물건들과 최대로 넣을 수 있는 무게가 주어진다. 이 때 최대 무게..
백준 9251 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 전 나의 생각 이 문제는 최장 공통 부분 수열(LCS)을 구해야 한다. 언뜻보면 같은 문자열만 구하면 되는 것이 아닌가 생각할 수 있지만 수열이기 때문에 값을 뛰어 넘는 부분까지 생각해야 한다. 1. if (i == 0 || j == 0) for문을 이용한 DP특성 상 이전에 저장된 값에 접근해야 하기 때문에 문자열을 1부터 시작하도..
