1. 문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 2. 풀이 DP + 트리 + DFS로 해결할 수 있는 문제. 그래프에 속한 사람은 얼리어답터일수도 있고 아닐 수도 있으며, 얼리어답터가 아닌 사람은 바로 인접한 노드 모두가 얼리어답터일때 아이디어를 받아드릴 수 있다. 이를 바탕으로 DP 식을 작성할 수 있다. dp[i][j] = r (0
1. 문제 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 2. 풀이 자두는 현재 1번 자두나무 아래에 위치해있다. 1번 움직인다면 2번 자두나무 아래에 위치하고, 2번 움직이면 1번 자두나무 아래에 위치할 것이다. 이를 일반화한다면 다음과 같다. 짝수번 움직일 경우 : 1번 자두나무 홀수번 움직일 경우 : 2번 자두나무 입력으로 자두가 떨어지는 자두나무의 번호가 주어질 때 나올 수 경우의 수는 어떻게 될까?? 내가 짝수번 움직였을 때 떨어지는 자두의 ..
1. 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 풀이 Point 두 문자열을 입력 받아서 표를 그려보았다. 표의 값은 맨 앞에서부터 탐색하는 지점까지 문자열을 비교하여 최대 몇 개가 겹치는지를 적었다. 예를 들어, 그림의 파란색의 경우 CA와 A를 비교한다. 이때는 최대 겹치는 구간이 A 하나이므로 1을 적는다. 그림의 초록색의 경우 CAPC와 AC를 비교한다. 이때는 최대 겹치는 구..
1. 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2. Error Point 없애야 하는 전깃줄 수를 구하기 위해 입력받은 전깃줄을 탐색하면서 하나라도 교차하면 카운트하는식으로 생각함 → 이 후 어찌 처리해야 하는지 감이 안옴 없애야 하는 전깃줄의 최소 개수를 구하기 위해 반대로 생각하여 전체 전깃줄 수 - 교차하지 않는 최대 전깃줄 수 = 없애야 하는 전깃줄의 최소 개수. 즉 교차하지 않는 최대 전깃줄 수를 구하고 전체 전깃줄 수에서 빼주면..
1. 문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 2. 풀이 Point 각 행 별로 선택할 수 있는 경우의 수는 세 가지다. (첫 번째, 두 번째, 세 번째) 그리고 각 경우의 수를 선택했을 때 다음을 고를 경우의 수는 세 가지이다. 따라서 0번 열, 1번 열, 2번 열을 각각 메모이제이션 해주어야 하므로 dp를 2차원 배열로 만든다. 각 경우의 수를 골랐을 때의 최대 값은 다음과 같은 형식으로 식을 세울 수 있다. 최소 값도 이와 마찬가지로 N -..
1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 Point dp[p] = r p의 수를 만들 수 있는 경우의 수 r 1 동전만 썻을 때의 개수, 1과 2 동전을 썻을 때의 개수, 1과 2와 5 동전을 썻을 때의 개수를 행렬로 그린다. 2가 있는 row의 경우 1과 2를 사용해서 1을 만들 수 있는 경우의 수를 의미한다. 하지만 2를 사용해서 1을 만들 수 있는 경우는 없으므로 1로만 만들 수 있는 경우의 수가 그대로 내려간다..
1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 풀이 백준 실버 3의 DP 문제이다. 정말 DP는 풀어도 풀어도 해결할 방법이 보이지 않는 것 같다.. 우선 이 문제를 보고 N이 주어졌을 때, (1), (2), (3)의 상황에 맞게 if문을 걸고 재귀를 타면서 문제를 풀었지만, 시간초과가 발생했다.(문제의 시간 제한이 0.15초이기도 했고 N이 최대 10^6이기도 했으니 어마어마한 시간이 걸렸을 것이다.) 해결점은 DP에서 찾을 수 있었다. 우선 DP 배열을 정의할 때 dp[i] = p; // 인덱스(i)를 1로 만들기 위한 최소의 연산횟수로..
1. 문제 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 2. 풀이 베낭 알고리즘 문제이다. 물건의 개수가 사람의 수가 되었고, 가방의 무게 제한 대신 체력이 존재한다. 처음에 문제를 해결할 때는 체력 제한을 조건문으로 판별하려다 실패했고, 다른 분의 풀이를 참고하여 문제를 해결했다. 2중 반복문으로 탐색을 진행하는데, health_arr의 인덱스보다 크거나 같을 때까지 탐색을 진행하는 것이 포인트이다. 이렇게 탐색하면 선택된 인덱스의 체력..
