백준, boj) 2482. 색상환 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 개요 주어진 색상환의 인접한 색을 고르지 않는 것처럼 인접한 두 색을 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하자. 3. 문제 힌트 dp문제이다. dp를 [n][k]로 설계하고, n은 현재 고를 수 있는 색의 수, k는 이때까지 고른 색의 수로 정의하자. 4. 문제 풀기 인접한색을 선택하는 경우는 dp를 계산하면서 배제하기 때문에, 3차 배열..
백준, boj) 1509. 팰린드롬 분할 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 2. 문제 개요 어떤 문자열을 팰린드롬으로 분할하려고 한다. 분할의 개수의 최솟값을 구하시오, 즉 원소의 개수가 최소가 되도록 해야 함. 3. 문제 힌트 처음에 분할의 최솟값이라고 하길래 분할하면 분할했지 분할의 최솟값은 뭐지?라고 생각했다. 질문란 이런 곳을 찾아보니 분할의 경우의 수가 아니고 분할했을 때 원..
boj, 백준) 1947. 선물 전달 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 문제 설명 대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오. 모든 사람은 선물은 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다. 3. 문제 힌트 기존의 그룹(n - 1명)에 최적화된 답을 알고 있다고 가정하자. n - 1명이 있는데, 새로운 사람x가 들어온다. ( 이제 n명이 됨. dp[n]을 구할 것. ) (1) x가 1번사람이 받은 선물과 바꾼다. (1번 사람의 선물이 아닌, 1번 사람이 받은 선물이다.) (2) x가..
백준, boj) 2316. 도시 왕복하기2 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방문했던 도시(1, 2번 도시 제외)를 두 번 이상 방문하지 않으려 한다. 한 번 1번 도시와 2번 도시 사이를 오갈 때, 반드시 한 개 이상의 도시를 중간에 거쳐야 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다 www.acmicpc.net 2. 문제 개요 N개의 도시가 P개의 양방향 길로 연결되어 있다. 1 --- 2 번 도시를 오갈 때, 반드시 1..
boj, 백준) 2812 크게만들기( C, C++ )
1. 문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 예제 입력 1 복사 4 2 1924 예제 출력 1 복사 94... www.acmicpc.net 2. 문제 개요 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램 작성하기. 3. 문제 힌트 시간 초과에 ..
boj, 백준) 9376. 탈옥 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어 www.acmicpc.net 2. 문제 개요 감옥에서 죄수 두 명을 탈옥시켜야 한다. 평면도에는 벽과 문이 나타나 있고, 탈옥시켜야 하는 죄수의 위치도 ..