백준

문제 : 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 이하로 되지 않게 하는 루틴을 짜면 된다. 정확히 루틴을 짜는 것이 아니라 가능한 경우의 수를 구하면 된다. 접근 방법 일단 가능한지 불가능한지를 확인하긴 위해선 루틴의 순서가 필요하다. 이 경우에는 순열을 사용해야 한다. 경우의 수를 모두 측정하기 위해선 모든 루틴을 탐..

문제 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 어떤 문제인가? 백 트랙킹의 대표적인 문제로 들었다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 물어보는 문제이다. 접근 방법 N이 4일 때 (1, 1)부터 퀸을 놓으면서 진행한다. 퀸은 대각선과 직선을 모두 공격할 수 없으므로 한 줄에 퀸이 놓이면 무조건 다음 줄로 넘어가야 한다. 그래서 두 번째 줄로 이동해서 다음 퀸을 놓을 자리를 찾는다. (2, 1), (2, 2)는 ..

문제 : https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 어떤 문제인가? 아주 간단한 문제이다. 그냥 가장 큰 첫 번째 링의 반지름과 각 링들의 반지름들을 비교한 다음 기약 분수 형태로 출력하면 된다. 접근 방법 int n; cin >> n; 링의 개수 n을 입력 받는다. int arr[n]; 링들의 반지름을 저장할 배열을 선언한다. for (int i = 0; i > arr[i]; } n번 만큼 링의 반지름을 입력받는다. 기약 분수로 나타내기 위..

문제 : https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 어떤 문제인가? 골드바흐라는 분께서 추측하신 정수론의 미해결 문제를 구현하는 문제이다. 다만, 입력된 n에 대한 골드바흐 파티션이 여러 개일 경우 두 소수의 차이가 가장 작은 것을 출력해야 한다. 접근 방법 이 문제에서도 에라토스테네스의 체가 사용된다. 잘 모른다면 에라토스테네스의 체에 대한 이해를 하고 이 글을 보는 것을 추천한다. bool arr[10000 + 1]..

문제 : https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 어떤 문제인가? 베르트랑과 채비 쇼프라는 분께서 만드신 명제를 구현하는 것이다. 입력한 수 n에 대해 n초과~2n이하의 범위에 존재하는 소수의 개수를 출력하면 된다. 접근 방법 여기서 에라토스테네스의 체라는 개념이 사용된다. 에라토스테네스의 체에 대해 모른다면 이해가 안 될 것이니 보는 것을 추천한다. bool arr[123456 * 2 + 1]; for (int i = 2; i