D, E번에서 많이 틀려먹었습니다 :blobsad: A. Welcom to SMUPC 단순히 반복문 돌려서 $i$번째 문자를 찾으면 됩니다. B. 우당탕탕 영화예매 $i$번째 줄에서 $K \leq$ (어떤 한 공간의 크기) 인 경우에 연속적으로 앉히는 방법을 생각해보자면, 어떤 한 공간의 크기를 $M$이라고 했을 때 나올 수 있는 경우의 수는 $M-K+1$이 됩니다. ($1$을 더하는 이유는 $M = 4, K = 3$일때를 생각해 보면 알 수 있습니다.) C. 모스부호 노가다입니다. D. 이상한 호텔의 송이 $h$를 층수, $w$를 호수라고 합시다. $h$는 $\log_{2}{N}+1$이라는 식을 얻을 수 있습니다. ($N=1$인경우 $1$층이므로 $+1$) $w$는 다음 식으로 구할 수 있습니다. $w..
BOJ
* 논리적 오류등의 지적은 환영합니다. * 스터디를 진행해주신 dk10211님께 감사드립니다. 수열 $A$, 수열 $B$에서 $x=i$일 때, $A_x$ 혹은 $B_x$중 하나만을 골라 정답 집합 $S$를 만든다고 할 때, $S$를 만들기 위한 최적해를 구하는 방법을 소개합니다. https://www.acmicpc.net/problem/17169 17169번: Eat Economically Ho has arrived in a secret place for her secret business trip. She knows her trip will take at most $N$ days or shorter but doesn't know the exact number of days she'll be there...
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 본 문제의 핵심은, pq를 사용해서 데드라인안에 최대한 점수를 많이 얻는 것을 목표로 해야합니다. 예를 들어, 4 1 1000 1 100 1 100 1 100 와 같은 데이터가 있다면, $w=1,000$인 과제를 선택하는 것이 최적해입니다. 7 4 60 4 40 1 20 2 50 3 30 4 10 6 5 예제의 메모에선, 데드라인이 빠른걸(낮은 것) 굳이 안해도 나중의 것을 선택했을 때 더 많은 $w$를 얻을 수 있음을 보여줍니다. 먼저, ..
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 본 문제는 $O(nm)$대신, $O(nlogm)$으로 접근할 수 있는 방법이 있습니다. ($n$, $m$은 $A_p$, $B_p$의 길이) 먼저, 배열 $A$, $B$에 대해서 가능한 모든 부분합을 $A_p$, $B_p$에 저장하는 과정을 각각 $O(N^2)$, $O(M^2)$으로 구해줍니다. 그 다음, $A_p$, ..
https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 본 문제의 핵심은, $x_i$를 가진 사람이 점수를 얻으려면 $p\times x_i$ ($p$는 $2$보다 크거나 같은 정수)가 존재해야 합니다. 즉, $1$보다 크거나 같고, $1,000,000$보다 작거나 같은 정수 범위 내에서 $x_i$를 가진 사람이 얻을 수 있는 점수(+)는, 이 범위 내에서의 $p\times x_i$를 가진 사람의 수 입니다. 잃는 점수는 이 사람의 수를 구하는 과정에서 $p\..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 본 문제의 요점은 '현재 상태에서 값이 작은 두 묶음을 합치는 것이 최적해이다.' 입니다. $A$를 최솟값이 앞으로 오도록 정렬한 배열이라고 합시다. 처음에는 정답이 $A_2 + \sum_{i=1}^{N} (A_i\times (N-i+1))$ 라고 생각했으나, 두 값을 합치는 과정에서(이때의 최소값들을 $Min_1$, $Min_2$라고 합시다.) 이 두 값보다 커지는 케이스가 발생합..
