컴굥일지

문제 https://www.acmicpc.net/problem/14713 문제 내용 앵무새들의 말로 문장 L을 만들 수 있는지 없는지 판단하는 문제이다. 문제 풀이 앵무새가 말하는 데에는 규칙이 있다. 1. 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다. 2. 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다. 3. 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다. 4. 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다. 위 규칙을 살펴보면, 1번과 2번 규칙을 통해서 문제 해결에 queue를 사용..

문제 https://www.acmicpc.net/problem/19941 문제 내용 햄버거 H와 사람 P의 순서가 표시된 문자열이 주어진다. 사람은 자기 주변으로 k만큼 거리 안에 있는 햄버거만 먹을 수 있다. 최대한 많은 사람이 햄버거를 먹을 수 있도록 할 때, 최대 사람 수를 구하면 된다. 문제 풀이 greedy한 문제이다. 사람을 기준으로 (-k~k) 범위 안에 있는 햄버거 중 가장 좌측에 있는 것을 먹도록 하면 된다. 햄버거를 먹으면 그 배열의 원소를 H나 P가 아닌 문자로 바꾸고 계속 탐색을 진행하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ..

문제 https://www.acmicpc.net/problem/11501 문제 내용 날 별로 주식의 가격이 주어진다. 이때 우리는 주식을 사거나 / 팔거나 / 아무것도 안 하거나 3가지 중에 골라야 한다. 최대 이익을 만들어 결과를 출력하면 된다. 문제 풀이 문제를 읽고 나서 가장 먼저 떠오르는 것은 앞에서부터 차례로 확인해나가는 방법이었다. 현재 구입하는 시점 이후에 가장 비쌀 때 팔아버리면 된다. 현재 구입 시점이 가장 비싸다면 사지 않으면 된다. 다만, 이 방법은 구현하기가 어려웠다. 현재 구입하는 시점 이후 중, 가장 비싼 때를 찾기가 어렵기 때문이다. 그래서 뒤에서부터 확인하기로 했다. 그렇게 되면 가장 비쌀 때를 먼저 확인하고 이후에 주식을 살 수 있다. 코드 #include #include ..

문제 https://www.acmicpc.net/problem/13413 문제 내용 문자열 두 개를 입력받아서 한 문자열을 다른 문자열로 바꾸기 위해 몇 번의 연산이 필요한지 계산하면 된다. 이때 연산의 종류로는 2가지가 있다. 1. 배치된 말 중에 임의의 2개의 말을 골라 서로의 위치를 바꾼다 2. 말 1개를 들어 뒤집는다 문제 풀이 초기 상태와 목표 상태에서 서로 일치하지 않는 위치에서 w와 b의 개수를 구한다. (초기 상태 기준으로 구했다) 잘 생각해보면 따로 계산할 것이 없이 큰 값이 결괏값이 된다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); /..

문제 https://www.acmicpc.net/problem/9237 문제 내용 묘목 하나를 심는데 1일이고, 묘목이 자라는 데 걸리는 시간은 주어진다. 묘목이 다 자라면 그다음 날에 이장님을 초대하려고 한다. 이때 이장님을 며칠 만에 초대할 수 있을지를 구하면 된다. 문제 풀이 크게 생각할것도 없이 무조건 자라는데 오래 걸리는 묘목부터 심어야 한다. (greedy 문제이다) 그래야 자라는 동안 새 묘목을 심어 최대한 기간이 겹치게 할 수 있다. 이를 위해서 sort()로 정렬해주었다. 이때, 내림차순으로 정렬하기 위해서 sort()의 세 번째 인자에 비교 함수 compare를 만들어 넣어 주었다. 내림차순으로 정렬이 완료되면, 이제 기간을 체크해야 한다. 문제에 주어진 예제 입력 1을 살펴보겠다. 아..

문제 https://www.acmicpc.net/problem/1946 문제 내용 선발할 수 있는 신입사원의 최대 인원수를 출력하는 문제이다. 이때 선발 조건은 서류 또는 면접 심사 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 것이다. 즉, 서류와 면접 심사가 남들보다 모두 뒤처진다면 탈락하게 된다. 문제 풀이 서류와 면접 점수를 pair로 입력받는다. 그리고 일단 서류 점수로 정렬을 한다. pair로 이뤄진 배열에 sort()를 쓰면 첫 번째 인자(서류 점수)의 순서대로 정렬이 된다. 이제 우리는 두번째 인자(면접 점수)를 비교하면 된다. 우리가 지금 판단하고자 하는 사람을 A라고 하면, A보다 서류 점수가 높은 면접자들보다 A의 면접 점수가 좋아야 한다. (면접 점수는 작을수록 좋..

문제 https://www.acmicpc.net/problem/13305 문제 내용 n개의 도시가 일직선으로 놓여있다. 2번째 줄에는 도시 간의 거리가 주어지고, 마지막 줄에는 각 도시별 주유소의 리터당 가격이 주어진다. 우리는 가장 왼쪽 도시에서 가장 오른쪽 도시로 가기 위한 최소 비용을 구하면 된다. 문제 풀이 입력받은 가격의 배열에서, 무조건 수가 작아질 때를 사용하는 것이 답이다. 즉, 지나가면서 최솟값을 계속 갱신해두고 가면 최소 비용을 얻을 수 있다. 위 설명에서 알 수 있듯이, 이 문제는 greedy 하게 풀 수 있다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin..

문제 https://www.acmicpc.net/problem/24544 문제 내용 콘텐츠의 개수 n이 주어지고, 그다음 줄에 콘텐츠의 흥미도가 주어진다. 마지막 줄에 등록 여부가 주어지는데 1이면 이미 등록되어 있는 경우, 0이면 그렇지 않은 경우이다. 문제에서 원하는 것은, 등록되지 않은 경우들의 콘텐츠 흥미도의 합이다. 문제 풀이 콘텐츠의 흥미도를 입력받아 저장해두고, 등록 여부를 입력받으면서 값을 더하면 된다. 다만, 출력 시에 첫째 줄에는 전체 콘텐츠의 흥미도 합을, 둘째 줄에는 미등록 콘텐츠의 흥미도 합을 출력해야 한다. 따라서 tot 변수는 전체 콘텐츠의 흥미도 합을, ans 변수는 미등록 콘텐츠의 흥미도 합을 더해가면 되겠다. 코드 #include #include #include using..

문제 https://www.acmicpc.net/problem/2579 문제 내용 계단을 오르면서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 난 dynamic programming으로 문제를 해결했다. 문제 풀이 계단을 오르는데에 규칙이 있다. 1번) 3개의 계단을 연속으로 밟지 못한다. => 연속해서 밟을 수 있는 계단은 2개뿐이다. 2번) 한 번에 한 계단 또는 두 계단을 오를 수 있다. => 한 칸은 건너뛸 수 있다. 이 규칙들을 따지며 규칙을 찾아보도록 하겠다. 빨간색 사각형이 계단을 밟는 경우, 엑스표가 밟지 않는 경우이다. 나올 수 있는 경우의 수는 2가지이다. 내가 지금 밟으려 하는 계단의 숫자가 n이라면, 1) n-2번째 계단을 반드시 밟고, n번째 계단을 밟는 경우 2) n-3번째 ..

문제 https://www.acmicpc.net/problem/2210 문제 내용 숫자판의 임의의 위치에서 시작하여, 5번 이동하면서 만들 수 있는 수의 개수를 출력하는 문제이다. 문제를 해결하기 위해 dfs를 사용했으며, 중복을 확인하기 위해 set을 사용했다. 문제 풀이 그렇게 어려운 문제는 아니다. 나는 dfs함수를 만들어서 재귀로 이 문제를 해결했다. 일단 5번을 이동하면 재귀를 끝낼 수 있도록 dfs()에 조건문을 넣어주었다. 다만, return을 하기 전에, set에 값을 집어넣어서 중복을 제거해주었다. 나중에 출력시 set.size() 해주면 된다. dfs()에서 탈출 조건을 넘어간다면, 상하좌우로 이동을 하도록 코드를 짰다. 이때 x,y좌표가 범위를 벗어나는 것을 방지하기 위해 체크를 해주..