문제 링크 www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 풀이 각 줄마다 사람을 앉힐 수 있는 각 조합을 상태로 생각합니다. 맨 앞줄부터 사람을 채워나간다고 합시다. $d[i][s]$: $i$번 줄에 조합 $s$로 사람을 앉힐 때 현재까지 앉을 수 있는 사람의 최댓값. 조합 $s$를 비트마스킹으로 관리할 수 있습니다. 어떤 자리에 사람을 앉히려고 할 때, 그사람의 바로 앞줄 대각선과 바로 옆에만 사람이 없으면 앉을 수 있습니다. 따라서 단순하게 위의 조건을 만족시키는 두 ..
링크 codeforces.com/contest/1496 Dashboard - Codeforces Round #706 (Div. 2) - Codeforces codeforces.com A번: 제출시간 00:24 문제 해석 + 이해하는데만 10분 넘게 걸린 것 같다.. 결국 $a_{k+1}$은 팰린드롬이든 아니든 상관없고, 나머지 $k$개는 각각 대칭되어야 한다. 그러니 양끝에서부터 같은 문자의 개수를 세준 뒤 $k$값과 비교하자. 문자열 길이가 짝수일때는 $a_{k+1}$의 길이가 적어도 2이상이어야 하므로 살짝의 예외처리가 필요하다. B번: 제출시간 00:46 분명히 빠르게 풀이를 짜고 구현했다고 생각했는데 20분이나 걸렸다.. 만약 초기 상태에서 $mex < max$인 경우 몇 번을 연산하든 $mex$..
문제 링크 www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음부터 예시를 들어 시뮬레이션해봅시다. 모든 과정이 자릿수만 다르지 똑같은 원리로 돌아갑니다. $n = 3, m = 2, k = 3$인 경우를 예로 들어보겠습니다. 1. 정답 구하기 step 1) 첫자리 알파벳을 우선 $a$로 결정한다고 가정합니다. 이때 가능한 문자열은 파랗게 칠한 6가지 문자열입니다. $aaabb$ $aabab$ $aabba$ $abaab$ $ababa$ $abbaa$ $baaab$ $baaba$ $babaa$ $bbaa..
문제 링크 www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 기본 논리는 간단합니다. 입력받은 두 문자열을 $u$, $v$라 하고, $i$는 $u$의 인덱스, $j$는 $v$의 인덱스라 합시다. 모든 $i$, $j$ 쌍에 대해 탐색하면서, $u[i]$ == $v[j]$ 인 지점에서 다음 문자부터 시작하는 최대 길이의 공통 부분 문자열의 길이값을 가지고 테이블을 업데이트해줍니다. 따로 정답을 저장하는 변수를 두어 그때그때 갱신하면 쉽게 짤 수 있..
문제 링크 www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 현재 클립보드에 들어있는 이모티콘의 개수와, 화면에 나타난 이모티콘의 개수를 바탕으로 상태를 정의합시다. $d[clip][screen]$: 클립보드에 $clip$개, 화면에 $screen$개 이모티콘이 있을 때 시간의 최솟값입니다. 한 상태에서 갈 수 있는 다른 상태가 명확합니다. 1) $clip$을 $screen$으로 변경 2) $screen$을 하나 삭제 3) $screen$을 $clip$만큼..
문제 링크 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 풀이 예제 설명을 색깔별로 친절하게 그려준 게 아마 큰 힌트가 되지 않을까 싶습니다. 1) 사다리를 쓰지 않고 이동할 수 있는 정점별로 그룹을 만들어줍니다. BFS, DFS 상관없습니다. 2) 위 그룹핑을 바탕으로 그래프를 재구성할 수 있습니다. 각 그룹을 정점으로, 그룹과 그룹 사이 사다리의 ..
문제 링크 www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 풀이 간단한 트리 DP 문제입니다. 1) 만약 현재 정점을 고르면 -> 자식들은 골라도 되고, 안골라도 됩니다. 2) 만약 현재 정점을 고르지 않으면 -> 모든 자식들을 골라야 합니다. $d[now][k]$를 k가 0일때 안고름, 1일 때 고르는 상황의 최솟값이라고 합시다. now의 모든 자식 next에 대해 $d[now][0] = \text{sum}(d[next][1])$ $d[now][1] ..
문제 링크 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 예제 2번으로 시뮬레이션해봅시다. 1번 비행기) 2번 게이트가 비어 들어갈 수 있습니다. 2번 비행기) 2번 게이트가 비어있지 않아 그 앞의 1번 게이트로 들어갑니다. 3번 비행기) 3번 게이트가 비어있어 들어갈 수 있습니다. 4번 비행기 3번, 2번, 1번 게이트가 모두 비어있지 않아 끝나게 됩니다. 문제를 풀어봅시다. 게이트의 수가 10만이라 그냥 시뮬레이션..
문제 링크 www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 풀이 1) 1부터 x 이하 모든 수의 1의 개수를 구해주는 함수 go를 구현합시다. 2) go$(B)$ - go$(A-1)$ 를 구해주면 됩니다! 이제 go함수를 만드는 방법을 알아봅시다. 1. 누적합 구하기 우선 최상위 비트가 $i$번 이하인 모든 수의 1의 개수의 합을 누적합으로 구해줘야 합니다. 편의상 $i$는 0부터 시작한다고 합시다. 이를 어떻게 구할 수 있을까요? ..
문제 링크 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 방향성 있는 그래프가 만들어집니다. 1) indgree가 0인 모든 배열을 큐에 넣어줍니다. 2) 위상 정렬을 돌립니다. 3) 어떤 팀에 속한다는 말은 곧 그래프에서 사이클을 이룬다는 말과 같습니다. 위상 정렬이 끝난 뒤 방문하지 못한 정점이 있다면, 그 정점은 사이클을 이룬다는 뜻입니다. 그러므로 위상 정렬 과정 중 방문한 정점의 개수를 출력해주면 됩니다. 정답 코드 #include using na..