kth990303의 코딩 블로그

알고리즘 스터디에서 나온 문제이다. 코드포스와 형식이 비슷해보여서 코포 연습 겸 블로그에 포스팅해보려 한다. 문제는 아래와 같다. https://www.acmicpc.net/problem/16288 16288번: Passport Control 입력은 표준입력을 사용한다. 첫 번째 줄에는 두 개의 정수 N 과 k 가 주어진다. N은 입국 승객의 수이며 k는 여권 심사 창구의 수이다. 단, 2 ≤ k ≤ N ≤ 100 이다. 그리고 두 번째 줄에는 승객이 입 www.acmicpc.net 문제가 잘 이해가 안돼서 [3, 1, 2]의 경우는 언제 가능한지 궁금했는데, Q1 (첫번째 통로)에 1, 2 / Q2에 3을 이동시킨 후에 출구로는 2번째 통로에서부터 나오게 하면 된다. 의식의 흐름 및 해설 이민을 가려 ..

감각 유지 겸 찾아본 문제. 많은 사람들이 풀었는데, 나는 안풀었길래 한 번 시도해보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 의식의 흐름 및 해설 매 초마다 자두를 가져가느냐, 안 가져가느냐에 따라 상태가 달라진다. 만약 같은 초에서 현재 움직인 횟수가 같은 경우, 그리고 위치가 같은 경우는 메모이제이션이 가능한 때이므로 dp로 풀 수 있다. 애초에 생긴 거부터가 dp처럼 생겼다. d[t][cnt][now]: 현재 t..

학교 채점현황을 둘러보다가 발견한 문제. KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다. 의식의 흐름 및 해설 처음에는 해결 방법이 떠오르지 않았다. 생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였..

추천받은 문제 중 하나. 문제는 아래와 같다. https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 의식의 흐름 및 해설 처음엔 평범한 knapsack인줄 알았는데, 생각해보니 자전거를 탈지, 도보로 갈지 선택을 해야되기 때문에 모든 경우를 선택하는 문제가 아니므로 knapsack dp가 아니었다. 따라서 top-down이든, bottom-up이든 시간복잡도 상 큰 차이가 없기 때문에 탑다운으로 풀었으며, N..

적당히 어려워보이면서 문제 이해가 쉬운 문제 찾다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net N N >> K; memset(d, -1, sizeof(d)); if (!K) { for (int i = 0; i < N; i++) { cout

오랜만에 가벼운 문제로 백준 포스팅을 들고와보았다~! 문제는 아래와 같다. https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호 관련 문제는 언제나 재밌다 재미는 개뿔...ㅠㅠ 의식의 흐름 및 해설 1. O(N^2) dp 괄호를 보면 보통 나는 stack을 떠올리는데, 이 문제는 경우의 수를 묻기 때문에 바로 dp를 떠올릴 수 있었다. 괄호 개수에 따라 충분히 메모이제이션이 가능하다는 사실은 한눈에 보이기 때문. 일단 N이 상당히 작은 데다가..

*주의* 정해와 다르게 해결하였으며, 정해 풀이는 올리지 않습니다. 스터디그룹 연습에서 B번으로 나온 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 의식의 흐름 및 해설 문제 이해가 조금 힘든데, 쉽게 풀이하자면 모든 포지션에 한 명 이상의 선수가 위치해야 된다. 모든 포지션에 선수가 위치해야 되므로 TSP와 똑같다. 그러므로 이 문제와 거의 유사하다. https://kth990303.tistory.com/61 [BOJ] 백준 1311. 할 ..

스터디그룹에서 진행한 연습 중 A번으로 나왔던 문제. 문제가 굉장히 긴데, 실생활에서 흔히 마주칠만한 좋은 문제였다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 의식의 흐름 및 해설 스키를 못타는 날이 중간에 껴 있더라도 이용권을 사용할 수 있어 문제 난이도가 낮아진 느낌. 만약 이런 조건이 없었다면 case_work가 좀 더 빡세졌을 것 같다. N이 100이기 때문에 시간복잡도가 상당히 널널하다. 현재 날짜에 스키를 탈 수 있다면 1일권, 3일권..

예전에 UCPC 연습용으로 풀다가 해결하지 못한 문제이다. 기댓값 표현이 겁을 한사발 먹게 해주기도 했고, 그 때 당시 dp를 어려워했기 때문이 아닐까 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 의식의 흐름 및 해설 먼저, 주사위값마다 행동에 영향을 끼치는 것은 확실하다. 마침, 주사위도 최근 3개의 결과만 영향을 미치기 때문에 dp[100000+1][6+1][6+1][6+1]의 재귀 탑다운dp로 접근해볼 수 ..

지난 포스팅에 knapsack은 탑다운보단 바텀업을 짜는 것이 훨씬 유리하다고 작성한 적이 있다. (아래 포스팅 참고) https://kth990303.tistory.com/207 [Knapsack] 냅색은 웬만해선 바텀업으로 짜자 knapsack dp를 알고 있는가? 아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100.. kth990303.tistory.com 이번 포스팅에선 knapsack 문제 유형을 익혀보고 공부해보는 시간을 가져볼 것이다. knapsack에서 개인적으로 중요하다 생각하는 것은 아래와 같다. 이 ..