[문제] 고급 주택의 청소만을 전문으로 하는 1인 기업 프리랜서 HCC(House Cleaning Company)가 있다. 이 사람은 소비자들의 요청을 미리 받아서 종합하여 그중에서 가장 이익이 많도록 작업을 선택 조정한다. 작업 단위는 일(daily) 단위이며 365*3(년)까지의 일정을 그전에 모두 확정한다. 사용자들은 자신의 집을 청소하기 원하는 기간(일단위)와 그때 지불할 비용을 Mr.X의 블로그에 올린다. 청소를 신청한 고객을 라고 할 때 이를 나타내는 신청 정보는 $(b_i, e_i, c_i)$로서 각각은 시작일과 종료일, 그리고 견적 비용(cost, 만원)을 나타낸다. 이 값은 조건, $1 \leq b_i \leq e_i \leq 365 * 3$을 항상 만족한다. 최소한 기간은 하루(a da..
533 [링크] [풀이] ps를 한창하던 2018년, 여름 즈음에 이 문제를 봤던 기억이 있다. 다른 알고리즘에 비해서 dp는 너무 어렵게 느껴져서, 풀다가 포기했던 기억이 난다. 아마 같이 문제를 봤던 형님은 얼마 안 가 풀었는데, 답지를 보자니 dp는 답지보면 너무 쉽게 느껴져서 다음에 풀어보기로 하고 군 입대를 했다.... 잡설은 뒤로하고, tree에서 dp를 쓰는 특이한 문제로 기억된다. 자, dp table $dp[i][j]$를 $j$가 0일 경우 => $i$번째 node가 얼리어답터가 아닐 때 $i$의 subtree를 완성시키는데(모두 수용하도록 하는데에) 필요한 최소 얼리어답터 수 $j$가 1일 경우 => $i$번째 node가 얼리어답터일 때 $i$의 subtree를 완성시키는데필요한 최소 ..
[문제] 부산 시민의 숙원사업인 돔 야구장을 부산 외곽 지역에 건립하고자 한다. 야구장 건립을 위해서 볼파크 공사 예정지는 아래 그림과 같이 $N \times M $ {0,1} 행렬(matrix)로 표시되며, 공사 예정지 내의 $k \times k$ 크기의 정방형 공간에 돔구장을 지으려고 한다. 그런데 이 지역의 어떤 지점에는 큰 암반이나 물구덩이가 있어서 해당 지점에서는 공사할 수가 없다. 아래 그림에서 $M_{i,j} = 1$ 은 위치 $(i , j)$에 지점에 엄청난 크기의 돌, 보호해야 할 정도의 큰 수목, 깊은 웅덩이 등의 장애물이 있음을 나타낸다. 그리고 $M_{i,j} = 0$ 은 해당 지점 $(i , j)$ 을 그대로 활용할 수 있음을 나타낸다. 우리는 이 예정 지역에 가장 큰 완전 $k ..
[문제] 막대(segment) 모양의 우주 정거장 2개 $S_1 = (A,B)$, $S_2 = (C,D)$ 가 있다. 이 두 우주 정거장을 연결하는 연결 통로(tube) $T$를 건설하려고 한다. 단, 우주에서의 공사작업은 매우 큰 비용이 들기 때문에 $T$의 길이는 최소화하려고 한다. 즉, $T$는 $S_1$과 $S_2$를 연결하는 최소 정수 길이의 선분이 되어야 한다. 정거장의 끝점이 통로의 연결점이 될 수도 있다. [입출력] 입력 파일 station.inp 의 4개 줄에 두 우주 정거장의 끝 점 $A,B,C,D$ 의 각 3차원 좌표 $(x, y, z)$가 3개 정수로 주어진다. 각 좌표의 범위는 $-10000 \leq x, y, z \leq 10000$이다. 여러분은 두 정거장을 연결하는 통로의 최..
[문제] 1부터 N까지의 정수가 쓰인 N 장의 카드로 진행되는 게임을 준비하고 있다. 이 N 장의 카드는 특별하게 고안된 셔플용 장치(Card Deck)로 들어가서 충분히 그리고 랜덤하게 섞이게 된다. 그런데 셔플 장치에서 섞인 카드 중에서 몇 장의 카드가 분실되었다는 사실을 알게 되었다. 즉 카드덱에 넣는 과정에서 실수로 몇 장의 카드가 빠진 것이다. 그리고 이 분실된 카드는 최대 2장이라는 사실도 알고 있다. 여러분은 이 셔플 장치에서 차례대로 나오는 카드를 모두 읽은 뒤 그 분실된 카드 번호를 찾아야 한다. 입력 파일에는 셔플 기계에 저장된 개의 카드 번호가 적혀있다. M은 $M = N - 1$ 혹은 $M = N - 2$이다. [입출력] 입력파일 deck.inp의 첫 줄에는 정수 N이 주어진다. 단..
[문제] 어떤 포털 사이트에서 특정 시간(time window)동안 수집된 전체 개의 단어(word) 기록이 있다. 이 중에서 과반(반을 넘는)인 $n / 2 + 1$회 이상 나타난 단어를 “인기 검색어”라고 한다. $n = 100$이라면 51번 이상 나타난 단어, $n = 501$이라면 251번 이상 출현한 단어가 인기 검색어이다. 어떤 경우에는 인기 검색어가 없는 경우도 있다. 예를 들어 인 단어 기록 {aa, ab, ac, aa, ad, ae}가 주어질 때, 이 경우에는 과반을 차지하는 단어가 없으므로 인기 검색어가 존재하지 않는다. 여러분은 주어진 단어 기록에서 인기 검색어를 찾아내는 프로그램을 작성해야 한다. [입출력] 입력파일 words.inp의 첫줄에는 입력 단어의 수를 나타내는 이 주어진다..
[문제] 회문(回文, palindrome)은 어떤 방향으로 읽어도 같은 문자열을 말한다. 예를 들면 “여보 안경 안 보여”, “다 큰 도라지라도 큰다.”, “아들딸이 다 컸다 이 딸들아”은 잘 알려진 회문이다. 이번에는 영문 소문자 문자열만 다룬다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체로는 회문이 아니지만 한 문자를 제거하여 회문으로 만들 수 있으면 이런 문자열을 “유사회문”(quasi palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하면 회문 ‘summus’이 되므로 이것은 유사회문이다. 여러분은 제시된 문자열이 그 자체로 회문인지, 또는 “유사회문”인지, 아니면 그 외 일반 문..
BOJ2401 약 2주일간 고생한 문제다. 해법은 kmp + dp로 간단한 편이나 시간초과가 날 리가 없는 시간복잡도인데 시간초과가 나버린다. 며칠간 생각해봐도 이 이상의 풀이를 생각해내기가 불가능하다고 판단해서 풀이를 봤는데, 풀이도 똑같은 풀이를 썼다. 한 주간 이것 저것 막 해보다가 발견해낸 차이점은 각각의 index에 matching된 문자열의 길이를 vector로 관리한 코드들은 전부 시간초과가 뜨고 배열로 관리한 코드들은 전부 ac가 됐다는 점이다. 이론상 push_back의 속도는 O(1)이지만 이게 Amortized O(1)이라는 점이 중요하다. 최악의 경우에는 O(n)의 시간복잡도를 갖기 때문에 함부로 O(1)이라고 판단하면 안 된다. 그래서 검색해보니 vector의 reserve를 사용..
딱 이 맘때 쯤 PS에 입문해서 STL쓰는 법 부터 완전탐색 DFS BFS DP 등등 배우기 시작해서 진짜 딱 1년 되는 시점이다. 그 때에도 3회 SCPC 접수를 하고 있었고, 이제 막 시작하는 입장이라 참가는 안 했었다. 1년이면 길다면 길고 짧다면 짧은 기간이지만 나름 괜찮은 속도로 성장한 것 같다. 물론 다른 높은 대학에서 PS하시는 분들 보면 1년만에 퍼플, 오렌지 달고 백준 1000문제 찍으시고 그러던데... 머리가 다른것도 있지만 문제 수 부터 거의 2배 차이나기 때문에 노력의 차이가 아닌가 싶다. 가끔 블로그 보다보면 나도 열심히 해야지 자극 받다가도 막상 하면 너무 힘들어서 금방 쉬러가거나 집중력이 흐트러진다. 아무튼, 1년동안에 공부한 것을 테스트하는 자리이기도 하고, 생에 첫 전국단위..
A. Polycarp's Pockets숫자가 적혀있는 코인이 $n$개 있다. 같은 숫자를 갖는 코인끼리는 같은 주머니에 넣지 못 할때, 필요한 최소 주머니 수를 구하는 문제다. 가장 많은 같은 값을 갖는 코인의 개수를 구하면 된다. B. Binary String Constructing$a$개의 0과 $b$개의 1을 사용하여 string을 구성하는데 $s[i] != s[i + 1]$인 원소의 개수가 총 $x$개 이어야한다. 그런 string을 출력하는 문제다. 먼저, $a$가 더 크다고 가정해보자. 그러면 0으로 string을 모두 채운 후 $b$개의 1을 적절히 박아넣으면 된다. 먼저 $s[0]$ 에1을 넣고 x를 1개 빼자. 그 다음, x가 2 이상일 때 까지 $s[n - 2]$부터 2칸 간격으로 1을..
