mojo's Blog

문제 링크 : 1543번: 문서 검색 (acmicpc.net) 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문제 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검..

문제 링크 => 1744번: 수 묶기 (acmicpc.net) 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디 알고리즘 문제이다. 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다. 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하도록..

문제 링크 => 1339번: 단어 수학 (acmicpc.net) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 그리디 알고리즘 문제이다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오...

문제 링크 => 19541번: 역학 조사 (acmicpc.net) 19541번: 역학 조사 2020년, 신종 전염병이 유행하여 UCPC국 질병관리본부에서 역학 조사를 하고 있다. UCPC국의 인구는 총 $N$명이며 각각 $1$, $2$, $\cdots$, $N$번의 주민번호가 붙어있다. 질병관리본부는 지금까지 $M$개의 www.acmicpc.net Greedy 알고리즘 문제이다. 이 문제는 시간순으로 모임의 정보가 주어져 있으며 전염된 결과를 제공해주기 때문에 역으로 접근하여 문제를 해결하면 풀리는 문제이다. 즉, 역순으로 해당 그룹에 있는사람들의 전염된 결과를 확인하고 모든 사람들이 전염된 경우와 한 사람이라도 전염되지 않은 경우 두 케이스를 나눠서 보는게 중요하다. 1. 모든 사람들이 전염된 경우 =..

문제 링크 => 19539번: 사과나무 (acmicpc.net) 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 그리디 알고리즘 문제이다. 1과 2를 동시에 사용하여 나열된 나무의 높이를 만들어 내도록 하는 문제이다. 이때 다음과 같은 예는 성립하지 않는다. [1 1 2 2 2] => 마지막에 2만 남으므로 성립하지 않음 [1 1 1 2 2 2 2] => 이 또한 마지막에 2만 남으므로 성립하지 않음 즉, 합이 3의배수가 아닌 경우는 무조건 "NO" 이다. 그리고 합이 3의 배수일때의 예를 살펴보도록 한다. [1 1 2 2] => 1, 2를 모두 사용하여..