Seondalgorithm

[BOJ][C++] 백준 9997번: 폰트

https://www.acmicpc.net/problem/9997 문제상근이는 자신이 만든 폰트를 테스트하기 위한 문장을 만들려고 한다. 폰트에는 알파벳 소문자만 포함되어 있기 때문에, 문장은 알파벳 소문자로 작성해야 한다.테스트 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야 한다.사실 문제를 많이 풀어본 사람이라면, 문제를 여기까지 읽어도 무슨 문제인지 감이 잡혀야 한다.상근이는 단어 N개가 포함되어 있는 사전을 하나 가지고 있다. 테스트 문장은 사전에 포함된 단어만 이용해서 만들 수 있으며, 각 단어는 한 번씩만 사용해야 한다. 또, 단어의 순서는 중요하지 않다. (“uvijek jedem sarmu” 와 “jedem sarmu uvijek”는 같은 문장이다)상근이가 만들 수 있는 테스트 문장..

https://www.acmicpc.net/problem/1365 문제공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.유스타운 시의 시..

https://www.acmicpc.net/problem/2421 문제홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다.홍태석은 소수를 좋아하는 것으로 서강대에서 유명하기 때문에, 첫째 저금통에 들어있는 돈의 양과 둘째 저금통의 돈의 양을 이어붙였을 때, 그것이 소수가 되는 것을 너무나도 좋아한다.예를 들어, 첫째 저금통에 12원이 있고, 둘째 저금통에 7원이 있다고 하자. 그럼 그 두 수를 이은 127은 소수가 된다.이제, 최대한 소수가 많이 나오도록, 홍태석이 돈을 넣는 최적의 순서를 찾아내면 된다. 가장 처음에 두 저금통에는 1원씩 들어있다.예를 들어,  N=4일 때를 ..

https://www.acmicpc.net/problem/2313 문제보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다.보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다.구매하는 보석의 가치의 총 합이 최대가 되도록 보석을 구매하는 방법을 찾아내는 프로그램을 작성하시오.입력첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 2×n개의 줄..

https://www.acmicpc.net/problem/1577 문제세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.따라서, 아래 그림과 같이 생겼다.세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오..

https://www.acmicpc.net/problem/4883 문제이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다.삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다.오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째..

https://www.acmicpc.net/problem/2688 문제어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T(1 출력각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다..

https://www.acmicpc.net/problem/18808 문제혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각 칸이 상하좌우로 모두 연결되어 있지 않다. ..

https://www.acmicpc.net/problem/2473 문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액..

https://www.acmicpc.net/problem/1593 문제마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 ..