본문 바로가기

백준25

BOJ 2295 - 세 수의 합 2295번: 세 수의 합 (acmicpc.net) 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 접근 방법 백트래킹, 브루트포스말고는 어떻게 풀어야할지 감이 안잡혔다. 그래서 결국 알고리즘 분류를 봤다... 이 문제에서 어떻게하면 이분탐색으로 풀수있을까 많이 생각해보았다. 무엇을 기준으로 대소비교를 할 것인가? 처음엔 원소의 인덱스를 기준으로 생각해보려고 했지만, 해당 원소의 더한 값을 구하려면 이전 원소들을 모두 3개씩 더해야 한다. 그리고 무엇을 기준으로 .. 2024. 4. 13.
BOJ 16401 - 과자 나눠주기 16401번: 과자 나눠주기 (acmicpc.net) 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 접근 방법 가장 길게 과자를 N명에게 나눠주는 문제이다. 이때 핵심이 과자를 부러뜨리면 다시 합칠 수 없다는 것이다. 예제 1을 보자. 1 2 3 4 5 6 7 8 9 10에서 3명에게 가장 긴 과자를 주려면 8 , 9 , 10을 선택하여 9와 10을 각각 1, 2 만큼 부러뜨려 8로 맞춰 주면된다. 예제 2번의 경우 한 번더.. 2024. 4. 13.
BOJ 16987 - 계란으로 계란치기 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 접근 방법 전형적인 백트래킹 문제이다. 순서대로 계란을 집어, 나머지 계란 중 하나를 치면 되는 문제이다. 이 문제의 핵심은 조건문을 어떻게 작성하냐 이다. 내가 틀렸던 예제는 다음과 같다. 3 1 4 8 1 3 1 // 정답: 2 손에 든 계란 외에 모든 계란이 깨진 경우를 체크해주지 않아 답이 1이 나왔다. 이를 bool flag를 통해 쉽게 수정하였다. 코드 #include #.. 2024. 2. 28.
[그리디 #19] BOJ 2812 - 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 심플하면서 어려운 문제이다. n자리 수에서 m개의 수를 제거하여 가장 큰 수를 만드는 문제이다. 예제 3번에 이 문제에 힌트가 있다. 4 1 7 7 2 5 2 8 4 1 에서 4개를 제거하여 775841 를 만들어야 한다. 핵심은 4와 1을 제거하여 7을 가장 높은 자릿수로 만들어야 한다는 것! 예전에 스택을 이용하여 괄호가 포함된 중위 표기법을 후위 표기법으로 고치던게 생각이 났다. 스택에 숫자들을 넣고, 현재 숫자보다 작은 숫자들은 제거하는 방식으로 진행하여 .. 2024. 2. 23.
[그리디 #18] BOJ 11000 - 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 접근 방법 저번에 풀었던 최소 회의실 개수와 같은 문제이다. https://parvegoongame.tistory.com/126 [그리디 #16] BOJ 19598 - 최소 회의실 개수 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 meteorfish.blo.. 2024. 2. 22.
[그리디 #17] BOJ 21314 - 민겸 수 https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 접근 방법 두를 최종적으로 계산하는 경우는 두가지 이다. 1. K가 왔을때 2. string이 끝날때 이 두 가지 경우는 최소와 최대 공통적으로 적용된다. 이제 세부적으로 최대와 최소를 구하는 알고리즘을 생각해보자. i) 최대 MKKMMK 의 경우, MK + K + MMK = 50 5 500 이다. K는 50을 곱해버리므로 무조건 M과 붙어야한다. 따라서, 알고리즘은 다음과 같다. 1. M이 왔을 경우, mCnt를 +1 한다. 2. K일 경우, mCnt를 이용하여 수를 계산 .. 2024. 2. 22.

티스토리툴바