BOJ 백준 6672 Electricity 문제: https://www.acmicpc.net/problem/6672 6672번: Electricity Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there i www.acmicpc.net 처음에는 문제 내용을 제대로 이해하지 못해서 난처했는데, 결국 간단히 정리..

BOJ 백준 17501 수식 트리 문제: https://www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net N개의 피연산자 노드와 N-1개 연산자 노드로 구성된 이진트리에서 피연산자 노드 정수 값을 원하는 만큼 서로 바꿨을 때 나올 수 있는 수식 트리의 최댓값을 구해야 한다. 문제에서는 노드에 있는 정수를 원하는 만큼 바꾸어서 수식 트리의 결과값이 최대가 되도록 한다고 서술했지만, 관점을 달리 바라보면 처음부터 트리를 구성할 때 원하는대로 노드의 정수값을..

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번)를 이전에 푼 적이 있어서 이와 유사한 문제라고 생각하고 접근했다. 그러나 해결 방법을 고민하면서 이전 것과는 전혀 다른 문제임을 알았다. 처음에는 이전 문제처럼 왼쪽 열에서부터 오른쪽 열로..