BOJ 백준 16472 고냥이 문제: https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제에서 주어지는 문자열을 S라고 하자. 이 문제는 크게 두 가지 풀이가 있다. 하나는 인식할 수 있는 문자열의 길이를 가지고 이분 탐색(Binary Search)하는 것과 다른 하나는 두 포인터(Two Pointer)를 사용해서 푸는 것이다. 1. 이분 탐색으로 풀기 이분 탐색 대상을 인식할 수 있는 문자열의 길이로 설정한다. 즉, 길이 mid만큼 연속되는 문자열을 ..

BOJ 백준 19535 ㄷㄷㄷㅈ 문제: https://www.acmicpc.net/problem/19535 19535번: ㄷㄷㄷㅈ 첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다. www.acmicpc.net 정점 수가 N인 트리가 주어졌을 때, 4개의 정점으로 이루어진 ㄷ’ 모양의 서브트리와 ‘ㅈ’ 모양의 서브트리 개수에 3배한 값을 비교하여 해당 트리가 어떤 트리에 속하는지 출력해야 한다. (4 ≤ N ≤ 300,000) 처음에 이 문제를 보고 (트리에서의) 다이나믹 프로그래밍(Dynamic Programming)으로 해결하는 문제일 것으로 예상했다. 그러나 실제로 확인해보니 굳이 거창하게 다이나믹 프로그래밍까지 확장하여 생각할 ..

BOJ 백준 14505 팰린드롬 개수 구하기 (Small) https://www.acmicpc.net/problem/14505 14505번: 팰린드롬 개수 구하기 (Small) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net 'BOJ 백준 14517번 팰린드롬 개수 구하기 (Large)'와 동일한 풀이로 해결 가능한 문제여서 BOJ 14517번을 기준으로 풀이했다. BOJ 백준 14517 팰린드롬 개수 구하기 (Large) https://www.acmicpc.net/problem/14517 1..

BOJ 백준 20667 크롬 문제: https://www.acmicpc.net/problem/20667 20667번: 크롬 첫 줄에는 N, M, K 값이 주어진다. (N ≤ 100, M ≤ 1,000, K ≤ 100,000) N 은 총 크롬 탭 수이다. M 은 목표 CPU 사용량이다. K 은 목표 메모리 할당량이다. 다음 N 줄에는 다음과 같이 크롬 탭의 정보가 www.acmicpc.net N개의 탭 중 일부 탭을 지워서 CPU 사용량을 M 이상, 메모리 사용량을 K 이상 확보하면서 지운 탭의 중요도의 합을 최소로 하는 것을 목표로 한다. 이 때의 중요도 합의 최솟값을 구해야 한다. 우선 이 문제는 다이나믹 프로그래밍(Dynamic Programming)으로 해결해야 한다. 그러면 여기서 다이나믹 프로그..

​​ BOJ 백준 11570 환상의 듀엣 문제: https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 상덕이와 희원이 두 사람이 서로 노래를 부를 때 악보에 적혀 있는 N개의 음을 순서대로 노래한다. 악보에서 서로 인접한 두 음의 높이 차이의 합이 노래를 할 때 힘든 정도이다. 상덕이와 희원이가 한 악보에 있는 N개의 음을 분담하여 노래할 때, 두 사람 각각의 힘든 정도의 합의 최솟값을 구해야 한다. N개의 음을 두 집합 A, B로 나누고 모든 음이 ..

BOJ 백준 1648 격자판 채우기 문제: https://www.acmicpc.net/problem/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net N × M 크기의 격자판을 2 × 1 또는 1 × 2 크기의 도미노로 채우는 방법의 수를 구해야 한다. 2 × M 크기의 격자판을 채우는 문제(BOJ 11726번)를 이전에 푼 적이 있어서 이와 유사한 문제라고 생각하고 접근했다. 그러나 해결 방법을 고민하면서 이전 것과는 전혀 다른 문제임을 알았다. 처음에는 이전 문제처럼 왼쪽 열에서부터 오른쪽 열로..

BOJ 백준 19645 햄최몇? 문제: https://www.acmicpc.net/problem/19645 19645번: 햄최몇? 세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다. 막내 길원이는 문득 중요한 사실을 www.acmicpc.net N개의 햄버거가 있고, 각 햄버거마다 먹을 때 얻을 수 있는 효용 값이 정해져 있다. 또한 섭취한 햄버거의 효용 값은 누적된다. 두 명의 선배와 막내 길원이가 모여서 N개의 햄버거를 먹을 때, 선배가 더 많은 효용을 얻게 하면서 막내가 얻을 수 있는 효용의 최댓값을 구하는 것이 문제이다. 처음에는 Dynamic Programming 풀이법으로 접근하여 다..

BOJ 백준 10160 암호 문제: https://www.acmicpc.net/problem/10160 10160번: 암호 새로 바뀐 KOI 웹사이트의 암호는 N개의 영문 알파벳 대문자로 이루어진다. 특별히 암호는 영문 알파벳 중 처음 K개를 사용해서 만든다. 예를 들어, K=5이면, ‘A', 'B', 'C', 'D', 'E'만으로 암호를 만들 www.acmicpc.net 길이가 N이고 영문 알파벳 중 처음 K개의 알파벳을 사용해서 만든 암호 중 안전한 암호의 개수를 구한다. 여기서 ‘안전한 암호’란 “ABCBC” 또는 “ABABC” 패턴이 없는 암호를 의미한다. 처음에는 여집합을 이용해서 구하는 방법을 고민했다. 전체 암호의 개수에서 안전하지 않은 암호의 개수를 구하면 안전한 암호의 개수를 알 수 있기..