1일1알

https://kjhcocomi.tistory.com/11 백준 11052번 카드 구매하기 C++ 한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 kjhcocomi.tistory.com 이 문제와 유사한 문제이다. 금액의 최대가 아닌 최솟값을 구하면 된다. 여기서는 최솟값을 구해야 하기 때문에 초기값을 넣어주어야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; t..

2차원 dp테이블 dp[n][m]을 이용해서 n에는 현재 곡의 번호, m은 볼륨 정보로 가능한지 가능하지 않은지 여부를 통해 dp테이블을 채우고, 마지막 곡에서 가장 큰 m의 값이 정답이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, s, m; vector volumes; int volume; int ans = -1..

간단한 dp문제처럼 보이지만 예외처리를 굉장히 많이 해줘야 한다. 푸는데 시간이 꽤 많이 걸렸다. 몇 가지 예를 들어보면 26일 때는 (26), (2, 6) 두 개가 가능하고 27은 (27) 한 개만 가능하다. 30은 불가능하지만 20은 가능하다. 110은 11까지만 봤을때는 (11), (1, 1) 두 개가 가능하지만 110까지 다 봤을 때는 110 하나만 가능하다. 이런 예외들을 처리하는게 상당히 까다로웠다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ..

A가 B를 신뢰하는 경우에 B를 해킹하면 A를 해킹할 수 있기 때문에 A와 B를 입력받았을 때 B->A 로 연결되어있다고 저장한 뒤 bfs로 탐색하여 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; vector trust(10001, vector()); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int a, b;..

우선 입력받은 집의 위치들을 오름차순으로 정렬한다. 가능한 최소 간격은 1, 최대 간격은 제일 오른쪽 집-제일 왼쪽 집 이다. left를 1, right를 house[n-1] - house[0] 으로 놓고 이분탐색을 하면서 답을 구할 수 있다. 설치한 공유기의 수가 C보다 크거나 같으면 간격을 넓혀야 하기 때문에 left를 mid+1로 바꾼 뒤 답을 갱신해주고, 설치한 공유기의 수가 C보다 작다면 간격을 좁혀야 하기 때문에 right를 mid-1로 바꾼다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; ty..

이분 탐색으로 해결할 수 있는 문제이다. 최소를 동영상의 길이의 최소로 하고, 최대를 동영상의 길이들의 총 합으로 시작해서 이분탐색을 하면서 가장 적절한 블루레이의 크기를 구할 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; int sum = 0; int arr[100001] = { 0 }; bool IsPossible(int value) { int cnt = 0; int sum = 0; for (int i = 0; i < n; i++) { ..