김머성 블로그

[BAE/<JOON> 문제풀이] 14925. 목장 건설하기

https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 풀이:: 목장 모양이 정확하게 정사각형이어야 하므로 DP[x][y] = 그 칸을 포함하며 좌상단으로 확장하는 정사각형 크기 중 MAX 으로 정의하면 dp[x - k][y - k] 값 들을 검사하다 이미 탐색된 값을 발견하면 해당 지점부터는 정사각형이 있는 것이 확정되므로 중복 계산하지 않을 수 있다. 맵으로 표현하면 다음과 같다. 1110 1110 1110 0000 이렇게 생긴 맵에서 좌상단부터 ..

[BAE/<JOON> 문제풀이] 1322. X 와 K

https://www.acmicpc.net/problem/1322 1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 핵심:: 비트 연산 구현 문제 풀이:: X | Y = X + Y 는 X와 Y를 2진수로 변환 했을 때 각 자리가 모두 다르다는 것을 의미한다. 따라서 주어진 X에 대해서 2진수 Y가 1을 사용할 수 있는 자리는 정해져 있다. X와 K의 최댓값은 2,000,000,000 이므로 계산해보면 2진수의 최대 자리수는 31자리 이다. X의 최댓값 2진수는 31자리이므로 그보다 큰 2 * 10^9 번째 수는 2^31 + (2 * 10^9) * 2^32 이다. 하지만 모든 자리가 1이어야 31자리 이상의 자..

[BAE/<JOON> 문제풀이] 1208. 부분 수열의 합 2

핵심:: MEET IN THE MIDDLE 개념 문제 풀이:: MEET IN THE MIDDLE 알고리즘은 1보다 큰 N에 대해 N^M 보다 N^(M/K) * K 가 더 작다는 아이디어로 만들어진 분할 정복의 일종이다. 숫자가 N개 주어질 때 모든 합의 가능 여부를 체크하려면 경우의 수가 2^N가지 있다. 2^40은 1,099,511,627,776 이므로 주어진 40개의 숫자를 전수 검사하는 방식으로는 시간 안에 해결 할 수 없다. 20개씩 나눠 첫 세트에 대해 전수 검사를 진행하고 S - 숫자 의 값이 두번째 세트에서 가능하다면 탐색을 종료한다. 탐색하는 S를 만드는 조합이 불가능한 경우가 최악의 경우로 이 때 탐색하는 횟수는 (2^20) * 2 = 2,097,152 이다. 의견:: 분할 정복은 쪼개진..

[BAE/<JOON> 문제풀이] 13334. 철로

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 핵심:: 문제 카테고리가 라인 스윕이고 정확한 풀이 로직이 정해져 있지 않아서 핵심을 정확하게 뭐라고 쓰기 애매하다. 강의실 문제와 비슷하여 해당 문제 풀이에서 영감을 받았다. 풀이:: 라인 스위핑은 기본적으로 주어진 배열 정렬하고 순회하며 답을 찾는 알고리즘을 의미한다. 시작 위치는 편의상 출근길의 시작 지점으로 고정한다. 주어진 L보다 출근길..

CodeForces #738 (Div. 2) Write-Up (A ~ D1)

A. Mocha and Math 문제 의역 모카는 고등학교를 다니는 소녀다. 그녀는 그녀의 선생님들에게 아주 흥미로운 지식을 배우는데, 그 중에서도 수학선생님이 가르쳐주는 지식이 가장 흥미롭다. 최근, 그녀는 이진법에 대해 배우고나서 이진 연산에 대해 깊은 흥미를 느꼈다. 오늘, 모카는 길이 n의 수열 a를 가지고 다음 작업을 원하는 만큼 수행할 것이다. 수열 a내의 임의의 구간 [l, r]을 설정 한 뒤, 구간안에 있는 모든 i에 대해 a[l + i]를 a[l + i] & a[r - i]로 대체한다. &연산자는 AND 비트연산이다. 예를들어 길이 5 짜리 배열 [a1, a2, a3, a4, a5] 에 구간 [2, 5]를 선택한다면 연산의 결과는 다음과 같을 것이다. [a1, a2 & a5, a3 & a..

CodeForces #742 (Div. 2) Write-Up (A - E)

A. Domino Disaster 문제 의역 엘리스에게 2개의 행과 n개의 열로 이루어진 격자가 있다. 그녀는 그 격자들을 N개의 1 X 2 크기의 도미노로 모두 덮고 싶다. 엘리스는 도미노를 마음대로 회전시켜 배치할 수 있다. 하지만 도미노가 서로 겹치게 배치할 수는 없다. 격자판을 모두 덮은 후, 엘리스는 밥에게 격자판의 두 행 중, 하나를 보여줬다. 밥을 도와서 격자판의 나머지 부분들을 맞춰보자! 입력 입력은 여러 개의 Test Case로 이루어져 있다. 첫번 째 줄에 정수 t ( 1 n; string s; cin >> s; for (auto v : s) { if (v == 'L' || v == 'R') { cout