JUINTINATION

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 n개의 집을 맞춰 빨강, 초록, 파랑 중 하나의 색으로 칠해야 하고 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 문제입니다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. n번 집의 색은 n-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ n-1)번 집의 색은 i-1번, i..

동적 계획법(dp)이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 메모이제이션을 통해 중복 계산을 방지하여 프로그램 실행 시간을 줄이는 방법 동적 계획법의 조건 어떤 문제(problem)가 여러 개의 하위 문제(sub problem)로 나누어지는 경우 하위 문제들의 답으로 어떤 문제를 해결할 수 있는 경우 서로 다른 문제에서 하위 문제들이 겹치는 경우 동적 계획법의 예시 dp를 사용하는 많은 문제 중에 피보나치 수를 구하는 문제가 있다. 피보나치 수는 다음과 같이 정의된다. fib(n) { if (n = 0) then return 0; else if (n = 1) then return 1; else return (fib(n - 1) + fib(n - 2)); } 이 문제는 재귀적 알고리즘..

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 일부 숫자 버튼이 고장 나있고 +1 혹은 -1만큼 채널을 변경할 수 있는 +, - 버튼이 있는 리모컨과 무한대만큼의 채널이 있을 때 100번 채널부터 n번 채널로 가기 위해 버튼을 최소 몇 번을 눌러야 하는지를 구하는 문제입니다. 코드 C언어 버튼을 누르는 최솟값 min은 원하는 채널 번호(n)와 현재 채널 위치(100)와의 차이로 초기화합니다. 이 경우는 + 또는 - ..

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 서로 다른 c개의 알파벳 소문자들을 사용하여 길이가 l인 다음 규칙을 만족하는 암호의 모든 경우를 출력하는 문제입니다. 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다. 알파벳이 암호에서 증가하는 순서로 배열되어있다. 코드 C언어 l과 c를 입력받은 후에 c개의 서로 다른 알파벳을 입력받기 전에 개행과 띄어쓰기를 표현하기 위해 getchar()를 사용했습..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 언어 AC의 두 가지 함수 R(배열에 있는 수의 순서 뒤집기)과 D(맨 앞의 수 버리기)를 이용하여 배열의 초기값에 대한 연산 결과를 구하는 문제입니다. 맨 앞의 수가 R 연산에 의해 바뀔 수 있기 때문에 덱을 사용하여 문제를 해결하였습니다. 코드 C언어 수행할 함수 p와 배열의 수의 개수 n를 입력받고 [x1,...,xn]과 같은 형태로 배열에 들어갈 정수를 입력받습니다. 이때 n을 입력받은 후에 개행을 하고 그다음에 '['를 입력해야 하기..

문제 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 이 문제에서의 알고리즘 캠프를 여는 기준은 다음과 같습니다. 문제는 2문제 이상이어야 한다. 난이도의 합은 L 이상, R 이하여야 한다. 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X 이상이어야 한다. 캠프에 사용할 문제를 고르는 경우의 수를 구해야 하는 문제이며 dfs를 이용하여 해결하였습니다. 코드 C언어 모든 입력을 받은 후에 qsort 함수를 이용하여 각 문제의 난이도가 담긴 정수 배열 arr를 정렬한 후에 dfs 함수를 실행합니다. 이때 함수의 매개변수는 처음부터 탐색하기 위해 i..