프로그래밍나무

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 접근방법 이 문제는 DP를 사용하였습니다. 먼저 팰린드롬은 뒤집어도 같은 것을 말합니다. 이 문제에 DP를 적용하기 위해서는 다음과 같은 생각을 해야 합니다. 1 2 1 이라는 숫자열이 있습니다. 이 문자열은 팰린드롬입니다. 이 문자열에 앞 뒤로 같은 숫자인 2를 추가해 보면 2 1 2 1 2 처럼 팰린드롬이 됩니다. 즉, 팰린드롬에 같은 숫자를 앞뒤로 추가하면 팰린드롬이 되는 겁니다. 이를 이용해 보겠습니다. 1 2 1 1 1 1, ..

https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 접근방법 이 문제에서는 이분탐색 + BFS를 이용하였습니다. 제 풀이는 다음과 같은 3단계로 구성되었습니다. 최댓값과 최솟값의 차이를 이분탐색을 이용하여 구합니다. 해당 차이를 가진 모든 경우의 수를 구합니다. 각 경우의 수마다 BFS를 통해 (1, 1)에서 (n, n)까지 이동할 수 있는지 체크합니다. 순서 배열의 수를 검사하여 전체 최댓값과 최솟값을 구합니다. 0 ~ (..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 접근방법 해당 문제에 이분탐색을 적용하여 해결하겠습니다. 이동하는 물품들의 중량을 정해놓고 가능한지 검사해나가면 중량의 최댓값을 구할 수 있습니다. 순서 각 다리의 중량 제한의 최댓값을 구한다. low = 0, high = 중량의 최댓값으로 설정 low와 high을 가지고 이분탐색 mid = (high + low) / 2 + 1 mid 중량으로 다리..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방법 해당 문제는 그리디 알고리즘을 이용해 풀 수 있습니다. 보석의 최대 가격을 구하기 위해서는 각각의 가방에 넣을 수 있는 보석 중 최대 가격을 가진 보석을 넣어야 합니다. 결국, 각 가방에 담을 수 있는 최대 무게보다 작은 보석 중에서 제일 큰 가격을 가지고 있는 보석을 선택하면 됩니다. 하지만 보석을 넣을 때는 최대 무게가 작..

접근방법 동전을 전부 배열에 넣어놓고 하나씩 꺼내면서 전체 배열을 갱신한다. 배열을 갱신할 때 해당 동전의 크기만큼의 앞의 원소를 해당 원소에 더한다. 예를 들어, 동전의 크기가 2일 때 a[i]=a[i]+a[i-2] 왜냐하면 동전의 크기가 2이면 i=2일 때는 동전 하나로 나타낼 수 있지만 i=4일 때는 동전 두 개로 나타내야 하기 때문이다. 코드 #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n, k; int coin[101], arr[10001] = { 0, }; cin >> n >> k; for (int i = 0; i > coin[i]; for ..