지속 가능한 꾸준함

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 본 문제는 동전들이 주어지고, 각각의 동전에 대한 가치(원으로 생각)가 주어집니다. 그리고, 이 동전으로 k 원을 만들어낼 수 있는지, 만들어낼 수 있다면 주어진 동전을 최소 몇개를 써야 k원을 만들어낼 수 있는지를 묻는 문제입니다. k원을 주어진 동전을 최소로 사용하여 만들기 위해서는 k원보다 작은 금액들을 먼저 최소로 사용하여 만들 수 있어야 합니다. 어떤 문제를 작은 문제..

www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 본 문제는 차례로 입력받은 원소를 저장하는 배열 A를 오름차순(=비내림차순)으로 정렬하기 위하여, 배열 A의 각 원소를 몇 번째 인덱스에 배치해야하는지를 찾는 문제입니다. 예제로 A = {2, 3, 1}이라는 배열이 주어졌을때, A의 원소 "2", "3", "1"을 오름차순이 되도록 배치시켜 재배치(A) = {1, 2, 3}이 되도록 배열의 원소를 재배치해야..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 본 문제는 시뮬레이션 문제입니다. 알고리즘은 문제의 규칙에 맞게 아래의 순으로 진행됩니다. 1. 미세먼지 확산 *미세먼지는 확산시, 미세먼지가 존재하는 칸에도 누적되는 방식으로 확산이 됩니다. 2. 미세먼지 이동 3. 위 과정(1. ~ 2.) T번 반복 문제를 풀다가 미세먼지를 시계/반시계 방향으로 이동시키는 부분을 깔끔하게 구현하는 ..

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제는 브루트포스 알고리즘을 사용하여 풀었습니다. 그런데 모든 경우를 일일히 탐색하는 것은 불가능합니다. NxN 체스판에 퀸 N 개를 놓을 수 있는 경우의 수는 \({{}_{N^2}\mathrm{C}_{N}}\) 이며 N = 15 일때, 91,005,567,811,177,478,095,440 가지의 경우를 고려해야합니다. 그렇기 때문에 우리는 퀸을 놓으며 걸러낼 수 있는 경우의 수는 최대한 걸러내야 합니다. 먼저, 문제 및..

www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 본 문제는 구현 및 시뮬레이션 문제입니다. 푸는데 2일 가량 걸렸을 정도로 저에게는 너무 어려운 문제였습니다. 제가 어려웠던점은 말을 쌓아야할때, 연결 관계를 코드로 구현해야하는 점이 어려웠습니다. 처음에는, 말이 쌓이며, 경우에따라 순서도 바뀌어야하니 데이터의 삽입과 Reverse 가 쉽게 가능한 자료구조를 생각해보았습니다. 좀 더 생각해보니 말이 얼마나 혹은 어떻게 쌓이든 바닥에 놓인 말과 가장 높이 놓인..

www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 � www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 솔루션을 참고하여 풀었으나 완전히 이해하고 푸는데 이틀씩이나 걸린 문제입니다. 해당 문제는 총 10차례동안 나온 주사위 값을 토대로 4마리의 말을 움직여 문제 규칙에따라 얻을 수 있는 점수의 최댓값을 출력하는 문제입니다. 저는 브루트 포스 알고리즘을 이용하여 해당 문제를 풀었습니다. 즉, 각 차례별로 나온 주사위 값에따라 4마리의 말..

www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 본 문제는 입력받은 휴가 일수 V 와 캠핑장의 연속 운영 일수 P, 캠핑장의 사용 가능 일수 L 간의 관계성을 찾으면 쉽게 모델링하여 해결할 수 있는 문제였습니다. 강산이가 캠핑장을 최대로 이용할 수 있는 일수를 Y 라 할때, Y 는 아래의 수식으로 부터 계산될 수 있습니다. Y = (V / P) x L + min(V % P, L) (1) (V / P) 의 결과는 정수형이다. 예시로 들어 설명하면 강산이의..

www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 간단한 DP 알고리즘으로 풀리는 문제입니다. 그런데, C++ 의 기본 정수 자료형(int, long long, unsigned long long 등)을 사용하여 다룰 수 있는 값보다 처리되는 값의 크기가 크다는 문제가 있었습니다. 이러한 큰 수를 처리할 수 있도록 string 자료형을 사용하였고, 연산 과정은 string 으로 표현된 10진 숫자를 Digit 단위로 접근하여 더하는 식으로 구현하였습니다. 주의할 점으로 2x0 직사각형을 채우는 방법의 수를 1로 두고 문제를..

www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 알고리즘 구현시 최적화를 굉장히 많이 신경써야 하는 문제였습니다. 알고리즘은 다음과 같습니다. 1. 두 백조 중, 한 백조를 고정시키고 나머지 한 백조를 이동시키며 방문할 수 있는 지역을 방문한다. 이 때, 고정된 백조가 있는 지역에 방문하면 현재 일자를 정답으로 출력한다. 2. 호수의 상태를 업데이트 한다. 3. 일자를 업데이..

www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 이제껏 푼 문제 중 가장 어려웠습니다... 다른 분들의 솔루션을 참고해도 이해가 잘 안될정도 였습니다... 먼저, n 자리 계단수의 수(큰 문제)는 n-1 자리 계단수의 수(작은 문제)로 계산될 수 있습니다(다이나믹 프로그래밍 기법을 이용하기에 적합함). 그런데, 문제에서는 단순히 n 자리 계단수의 수를 묻지 않고 n 자리 계단수 중에서 0, 1, 2, ..., 9 를 모두 포함하는 계단수의 수를 묻고있습니다. 이는 문제를 복잡하게 만드는 요소로 이를 계산하기..