문제 링크 www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 눈물 줄줄 흘리면서 풀었습니다 ㄹㅇ 이거 제 기준으론 골드 아닙니다.. 아마 더 쉬운 방법으로 구현하거나 규칙을 찾을 수 있을듯한데 그거 생각하는 것만 해도 골드는 아닌 것 같습니다. 백준 9527 - 1의 개수 세기 저는 위 문제와 유사한 방법으로 풀었습니다. 차이점은 2진수가 아니라 10진수고, 0의 개수까지 세주어야 해서 사고 회로가 터져나갑니다. 어쨌든 정답을 구하는 근본 논리는 위 문제와 같습니다. 해당 글을 먼저 참고해주세요. 누적합 배열을 정의해봅시..
문제 링크 www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 풀이 저는 경로 추적이 생각보다 까다롭게 느껴졌습니다. 1번, 2번 경찰차가 각각 몇번 사건을 해결했는지를 상태로 둡시다. $i$번 사건을 1번, 2번 경찰차가 해결하는 각 경우에 대해, (경찰차의 마지막 위치 ~ $i$번 사건이 일어난 곳의 위치) 사이 거리를 더해주며 최솟값을 갱신하면 됩니다. 경로추적은 의외로 간단합니다. 발생한 사건을 순서대로 보며, $i$번 사건을 1번 경찰차가 ..
문제 링크 www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 풀이 눈물겹게 풀었습니다... 😢😢😢 $i$번 칸의 위아래 각각 1) 선택하지 않음(앞에서 오른쪽 칸을 먹은 상태) 2) 한 칸만 선택 3) 오른쪽과 함께 선택 의 3*3가지 상태와 $i$번의 위, 아래칸을 함께 선택하는 상태로 총 10가지 경우가 있습니다. 각 상태에 따라 어떤 상태로 전이할지 정해주고 DP를 돌리면 됩니다. 맵이 원형이므로 첫 칸에서 가..
문제 링크 www.acmicpc.net/problem/5893 5893번: 17배 첫째 줄에 이진수 N이 주어진다. N은 최대 1000자리인 이진수이며, 0이 들어오는 경우는 없다. www.acmicpc.net 풀이 17 = 10001(2) 입니다. 입력받은 이진수를 왼쪽 4칸 쉬프트 해주고, 다시 그 이진수와 더해주면 17을 곱해준 것과 같습니다. 범위가 크니까 큰 수 덧셈을 구현해줍시다. 정답 코드 #include #define all(x) (x).begin(), (x).end() using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string u, v, ans; cin >> u; v = u; u +..
문제 링크 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) 위 그룹핑을 바탕으로 그래프를 재구성할 수 있습니다. 각 그룹을 정점으로, 그룹과 그룹 사이 사다리의 ..