백준

1. 문제 풀이 백준에 등록된 태그에는 그리디라고 나왔지만 저는 parametric search를 사용하여 풀이하였습니다. 고기를 특정 금액만큼 사기로 이분 탐색으로 결정합니다. 고기의 가격이 특정 금액보다 작거나 같은 경우를 찾아 mx에 저장합니다. mx와 비용이 같으며 아직 수중에 돈이 남아있는 경우 해당 고기를 사기로 결정하고, mx보다 작은 고기는 무게만 추가하는 로직을 추가하여 순회합니다. 이때, 구매하거나 덤으로 받은 고기들의 무게 총합이 M 이상인지 검사하면 됩니다.2. 소요 시간 및 경과시작 시간: 12시 08분#1 제출 시간: 12시 18분4% WA오버플로우인지 검사하기로 결정#2 제출 시간: 12시 20분4% WA오버플로우가 아님, 최대 금액과 같은 고기는 별도로 구매해야 된다는 사실을..

1. 문제 풀이 문제 유형은 그리디입니다. 코드포스에서 나올법한 문제였습니다.  정수 N, K에 대해서 임의의 문자열 S는 다음과 같은 조건을 만족합니다.문자열 S의 길이는 N이고, 'A' 또는 'B' 문자로만 이루어져 있다.문자열 S는 0 N, K를 입력받은 다음, 'B'로만 이루어진 길이 N의 문자열을 선언합니다.루프를 돌면서 현재 위치 idx에 대해서 S[idx]를 A로 바꾸었을 때, 두 번째 조건을 만족하는 쌍이 몇 개 나오는지 검사합니다. 여기서 [ 0, idx ) 구간에서 'A'로 바꾼 횟수를 세어야 합니다. S[idx] 문자를 'B'에서 'A'로 바꾸게 된다면 이전에 계산했었던 쌍의 개수가 변동되기 때문 AABBB는 2 번째 조건을 만족하는 ( i , j ) 쌍이 6개 존재합니다. 여기서 A..

1. 문제 풀이 문제 유형은 다이나믹 프로그래밍입니다. top-down approach로 풀이했습니다. dp 테이블 정의는 다음과 같습니다. dp[T][idx] : [ idx, k )번째의 동전으로 T원을 만드는 경우의 수 2. 소요 시간 및 경과시작 시간: 20시 23분#1 제출 시간: 20시 37분4% WA#2 제출 시간: 21시 27분AC총 소요 시간: 64분 3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector v..

1. 문제 풀이 문제 유형은 수학입니다. 숫자들을 자릿수로 분리해서 생각해봅니다.1 자릿수수: 9개숫자 총 개수 : 9개2 자릿수수: 90개 ( [ 10, 99 ] )숫자 총 개수: 180개3 자릿수수: 900개 ( [ 100, 999 ] )숫자 총 개수: 2700개이러한 규칙을 바탕으로 k번째 자리 숫자가 무슨 수인지 알아내는 방법을 구현해야 합니다. 이때, 다음과 같은 정의를 내릴 수 있습니다.N 자릿수는 각 수마다 N개의 자리를 차지한다. K가 가리키는 자리 숫자를 포함하는 수가 digit 자릿수라고한다면, digit 자릿 수 이전 자릿수들의 숫자 총 개수만큼을 뺌으로써 digit 자릿수 수들만 이은 문자열의 위치 값을 1-indexed가 됩니다.  K -= 1 * 9 + 2 * 90 + ... +..

1. 문제 풀이 문제 유형은 너비 우선 탐색(flood fill 기법)과 시뮬레이션, flood fill로 연합을 이루는 국가끼리 묶는다. 이때, 연합을 이루는 칸의 개수의 인구의 총 수를 연산해 주고 둘을 나눈 값을 저장한다. 이 값을 기준으로 연합마다 인구를 분산하여 저장하는 루프를 반복한다. 연합의 개수가 n * n이면 경계선이 열리지 않았다는 뜻이므로 종료한다. 2. 소요 시간 및 경과시작 시간: 16시 27분#1 제출 시간: 17시 05분AC3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typed..

1. 문제 풀이 문제 유형은 parametric search와 dijkstra입니다. 우선 이분 탐색으로 1번 컴퓨터에서 N번 컴퓨터를 연결하는데 최대로 사용할 수 있는 금액 cost를 결정합니다. 이후 간선의 가중치 정보를 cost에 맞추어 재가공하는데 cost보다 작거나 같다면 0으로 크다면 1로 간주하여 N번 컴퓨터까지 연결하는데 cost보다 비용이 큰 케이블의 개수가 몇 개인지 구합니다. 만약 d[n]에 저장되어 있는 값이 k보다 작거나 같다면 해당 cost로 탐색이 가능하다고 간주할 수 있습니다. 2. 소요 시간 및 경과시작 시간: 15시 16분#1 제출 시간: 16시 06분67% WA원인: N번 컴퓨터를 연결 못하는 경우를 구현하지 않음#2 제출 시간: 16시 12분67% WA#3 제출 시간:..

1. 문제 풀이 문제 유형은 투 포인터입니다. 보석 종류가 문자열로 주어지기 때문에 해시를 사용하여 보석 종류마다 숫자를 부여해 줍니다. 투 포인터를 사용하여 모든 보석을 포함하는 구간을 찾아 그 구간의 길이가 최소가 될 경우 갱신해 주는 방법을 사용했습니다. 투 포인터를 알고 있다면 무난하게 풀 수 있을 것 같습니다. 2. 코드#include using namespace std;int mx;unordered_map idx;vector solution(vector G) { for(auto x : G) { if(idx.find(x) == idx.end()) { idx[x] = mx++; } } int ansx{0}, ansy{100'000}; ..

1. 문제 풀이 문제 유형은 너비 우선 탐색입니다. multi-source bfs를 진행하여 풀이하는데 주의할 점은 물이 차있는 지역에 대한 정보를 먼저 큐에 삽입해야 합니다. 그 뒤에 고슴도치 위치 정보를 삽입하여 물인지 고슴도치인지 판별하여 다른 작업을 수행해 주면 됩니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef ..