분류 전체보기

문제 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 어떤 문제인가? 2*n크기의 직사각형을 1*2, 2*1의 타일로 채우는 방법의 수를 구하는 것이다. 간단한 dp문제이다. 접근 방법 n이 1일 때 2*1 타일만을 사용해 한 가지 방법밖에 없다. n이 2일 때 2*1 타일 두 개를 사용하는 방법 1*2 타일 두 개를 사용하는 방법 두 가지 방법 n이 3일 때 세 가지 방법 n이 4일 때 다섯 가지 방법 규칙이 보이는가? n이 3 이상일 때 dp[ n ] = d..

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 어떤 문제인가? 설탕을 n킬로그램을 배달해야 한다. 설탕은 3kg, 5kg 봉지로만 존재해 이 두 가지 종류의 봉지만 사용하여 배달을 해야 한다. 이때, 배달에 필요한 최소 봉지의 개수를 출력하면 된다. 이 문제는 예전에 그리디 알고리즘을 공부할 때 풀었던 문제이다. 지금은 다이내믹 프로그래밍을 공부 중인데 문제가 있어서 이번엔 dp로 풀어보았다. https://codegarden-farmjun.t..

문제 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 어떤 문제인가? 이친수라는 문제에서 정의된 이진수들이 있다. n이 입력됐을 때 n자리 이친수의 개수를 출력하면 된다. 접근 방법 일단 문제가 dp(다이나믹 프로그래밍)이라는 것은 문제를 읽으면 알 수 있다. 그러므로 점화식을 세워야한다. n = 1일 때 1 1개 n = 2일 때 10 1개 n = 3일 때 101 100 2개 n = 4일 때 1001 1010 1000 3개 . ...

문제 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 어떤 문제인가? 1부터 짝수인 n까지의 사람이 있다. 팀을 n/2, n/2명으로 두 팀으로 나눈다. 이때, 각 팀원들의 능력치를 합산해서 두 팀의 최종 능력치를 구한다. 그다음, 두 팀의 최종 능력치가 최솟값을 구하면 된다. 접근 방법 팀원들을 나누는 방법은 조합을 사용해서 가능한 모든 경우의 수를 탐색하면 된다. n명 중 n/2명을 뽑으면 나머지 인원들이 다른 팀이 되기 때문이다. int n; int arr..

문제 : https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 어떤 문제인가? 시작 전, 이 문제를 보니 어렸을 때 마인크래프트를 하던 기억이 떠올라 기분이 좋았다. 모든 입력들(땅의 높이)의 값이 같게 만들어야 하고 이때 걸리는 시간과 가장 큰 높이를 출력하면 된다. 접근 방법 int block[500][500]; 먼저 땅이 높이를 저장할 2차원 배열을 선언해줬다. int n, m, b; cin >> n >> m >> b; for (int i =..

문제 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 어떤 문제인가? n개의 숫자와 n-1개의 연산자를 입력받는다. 그렇게 되면 만들 수 있는 식이 여러 개 생기게 된다. 이때 모든 식을 계산했을 때의 최댓값과 최솟값을 출력하면 된다. 특이한 점은 식을 계산할 때 연산자의 우선순위를 고려하지 않고 식의 앞쪽부터 차례대로 계산하는 것이다. 접근 방법 vector num; vector op..

문제 : https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 > n; if (n == 0) { break; } vector arr; vector comb(6); for (int i = 0; i > a; arr.push_back(a); } combination(a..

문제 : https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 어떤 문제인가? 배열이 있을 때 | A [0] - A [1] | + | A [1] - A [2] | +... + | A [N-2] - A [N-1] |의 값이 최대가 되게 배열을 재배치해야 한다. 배열을 재배치하고 난 후 얻을 수 있는 최댓값을 출력하면 된다. 접근 방법 숫자를 재배치하기 위해서는 어떤 숫자를 어디에 배치해야 할지를 결정해야 한다. 따라서 데이터는 앞, 뒤 삭제 삽입 연산이 간편한 de..

문제 : https://www.acmicpc.net/problem/16457 16457번: 단풍잎 이야기 첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다. 둘째 줄부터 m개의 줄에는 각각 www.acmicpc.net 어떤 문제인가? m개의 퀘스트가 존재한다. 각 퀘스트는 k개의 스킬을 써서 완료할 수 있다. 1부터 2*n까지의 정수 중 n개를 뽑는다. 이때의 정수가 퀘스트를 완료할 때 필요한 스킬이다. 이때 퀘스트를 가장 많이 완료할 수 있는 경우를 찾으면 된다. 접근 방법 int n, m, k; int quest[101][10]; 문제에서 주어진 변수와 입력된 퀘스트를 ..

문제 : https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 어떤 문제인가? ㅋㅋㅋ참 웃긴 문제이다. 간단하게 문제를 설명하자면 하루에 운동을 마쳤을 때 중량이 500 이하로 되지 않게 하는 루틴을 짜면 된다. 정확히 루틴을 짜는 것이 아니라 가능한 경우의 수를 구하면 된다. 접근 방법 일단 가능한지 불가능한지를 확인하긴 위해선 루틴의 순서가 필요하다. 이 경우에는 순열을 사용해야 한다. 경우의 수를 모두 측정하기 위해선 모든 루틴을 탐..