MZ 개발자

이 문제의 핵심은 모든 통나무 조각 길이보다 큰 경우를 만족하는 적절한 길이의 통나무를 구하는 문제이다. 예를들어 L =9, K=2, C=1 일 경우 나올수 있는 통나무 조각은 4,1,4이다. 이때 모든 통나무 조각 길이 보다 긴 적절한 길이의 통나무를 구해야한다. 우리가 생각해야하는 조건은 두가지이다. 1. 모든 잘린 통나무 조각은 적절히 자를수 있는 최대 길이(mid)로 모두 자를 수 있어야 한다. 2. 자를수 있는 횟수를 초과 하면 안된다. 이를 바탕으로 풀이를 다음과 같이 생각해볼 수 있다. 1. 만약 잘린 통나무 누적 길이가 mid보다 커지는 순간까지 cut을 하지 않고, 커지는 순간 cnt을 증가시켜준다. 2. 이후 마지막으로 누적한 통나무의 길이가 mid 보다 클경우 위의 조건 1을 만족하지..

가장 기본적인 그리디를 연습할 수 있는 문제이다. 조금더 실전과 같은 훈련을 하기 위해 타이머를 설정하고 문제를 풀었다. 비교적 쉬운 난이도여서 약 8분정도 만에 문제를 해결하였다. 풀이방법은 N개의 동전을 가치가 가장 큰 순서대로 정렬을 한다. 그리디는 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 따라서 동전 개수를 최소한으로 하기 위해 선택의 순간마다 가치의 합 K를 결정할때 K보다 작은 동전중 가장 큰 가치를 가진 동전을 선택하면 된다. 예를들어 예시가 다음과 같이 주어졌을경우 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 4200원 보다 작은 동전 중 가치가 가장 큰 1000을 고르면 된다. 이후 1..

첫째 줄에 물이 새는 곳의 개수 N과 테이프 길이L 이 주어진다. 풀이방법은 시작점(start)을 잡고 시작점을 기준으로 물이 새는 곳(v[i]) 까지 거리가 L > n >> l; for(int i = 0; i > num; v.push_back(num); } if(l == 1) { cout

NxN 행렬로 동전이 앞 뒤로 놓여 있고 1번 연산에 행 또는 열 전체를 뒤집을 수 있다. 이때 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제이다. 이 문제를 완전 탐색을 한다면 행을 바꿀때마다 열의 상태도 같이 변한다. 따라서 행을 바꾸는 경우의수 2^20, 열을 바꾸는 경우의수 2^20 총 2^40이 된다. 루트포스 알고리즘을 이용하여 완전 탐색을 한다면 시간 초과 발생 핵심은 우리의 목표는 T가 최소가 되도록 뒤집어야 한다. 만약에 어떤 상태를 미리 알 수 있다면 그 상태에서 어떤 행 또는 열을 뒤집을지 빠르게 판단할 수 있다. 여기서 어떤 상태를 미리 알기위해 비트마스킹 개념을 도입한다. 비트마스킹이란 n

동전의 갯수가 최소가 되기 위해 5원짜리를 최대한 많이 사용하여 거슬러주면된다. 하지만 여기서 핵심은 무조건 5원짜리를 가자 많이 사용한다고 최대가 되지 않는다. 예를들어 13원일 경우 5원 2개로 거슬러주면 나머지 3원은 2원 짜리로 거슬러 줄 수 없다. 따라서 5원 1개 2원 4개 총 5개의 동전이 최소가 된다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int result = 99999999; for(int i = 0; i n) { cout

다음 두가지 조건을 역으로 계산 하여 B 에서 A로 만들수 있는지 없는지 찾아가면 된다. 이때 중요한점은 B가 홀수 인지 짝수 인지 판단하고, 홀수일경우 일의 자리가 1 인지 아닌지 확인하고 1이 아닐경우 A를 절때 만들 수 없다는 것을 찾아내면 된다. 만약 B가 짝수라면 2로 계속 나눠준면된다. 위의 조건을 적용하여 새로 만들어진 B`이 A보다 작아진경우 반복문을 멈추고 A와 B`이 같을경우 결과에 1을 더해준다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int a, b; cin >> a >> b; int result = 0; while(b > a) { if(b % 2 ..

두 수를 묶거나 더하여 합이 최대가 되게 하는 문제이다. 상식적으로 오름 차순으로 정렬하여 앞에서부터 두개씩 묶으면 될것 같은 생각이 들지만 문제에서 음수와 0이 존재하기 때문에 다른 방법을 선택하야한다. 경우의 수는 1. 모두 양수인 경우 2. 음수의 갯수가 짝수이면서 0이 포함 된 경우 3. 음수의 갯수가 홀수이면서 0이 포함된경우 한편 묶음의 기준은 두 수를 뽑은 후 두 수의 곱이 합보다 클경우 묶어주면 된다. (즉 a*b > a+b) 따라서 입력을 양수,음수로 나눈 후 각각을 조건에 맞게 독립적으로 계산하고 이후 두 결과를 합하면 된다. #include #include #include #include using namespace std; bool cmp(int a, int b) { return a..

N개의 단어가 주어졌을 때 알파벳의 숫자(0~9)를 결정하고 단어를 숫자로 치환하여 수의 합을 최대로 만드는 문제이다. 처음에는 자릿수를 생각하지 않고 단순히 길이가 긴 단어의 첫번째 알파벳을 큰 값으로 설정하면 될것 같다고 생각하였다. 그래서 N개의 단어를 길이 기준으로 우선순위 큐에 넣고 하나씩 뽑으면서 subString을 구한 후 다시 큐에 넣어주는 방법으로 구현하였다. 예제는 모두 통과하였지만 1%에 틀렸다고 나왔다. 😂 그리고 질문 개시판을 확인해보다가 반례를 찾을 수 있었고 틀린 이유는 각 알파벳 마다 자릿수 가중치가 존재하고 이 가중치에 따라 결과가 달라질 수 있다는 것을 알게 되었다. 예를들어 N=10 ABB BC BC BC BC BC BC BC BC BC 다음과 같이 주어졌을 경우 길이를..

문자열 파싱을 연습해볼수 있는 괜찮은 문제이다. 풀이 방법은 여러가지 존재하는데 보통 풀이는 다음과 같다. 최솟값을 만들기 위해 가능한 가장 큰 숫자를 빼야 한다. 따라서 - 를 기준으로 문자를 나누고 다음 - 를 만나기 전까지 모두 더해서 한번에 빼주면 된다. 나는 조금 고전적이지만 스택을 사용하여 숫자와 - 기호를 쌓았다. 이후 하나씩 빼면서 - 를 만나기 전까지 결과를 모두 더하고 - 를 만나면 더한 값을 -1곱하여 누적 시켜주었다. #include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; stack..

이 문제를 풀면서 아직 실력이 많이 부족하다는 것을 느꼈다. 처음 생각해낸 방법은 덱을 사용해서 문제마다 모든 조건을 처리해주는 정신 나간 짓을 하려고 하였다. 2번 3번 조건을 만족하기 위해 현재 내가 풀고있는 문제(now)가 있고 이 문제를 풀기 이전 풀어야할 문제(pre)를 설정하고 이상한 뻘짓을 많이 하였다... 문제를 보는 순간 어떤 알고리즘을 물어보는지 감이 오지 않아 어떻게든 내가 알고있는 알고리즘 내에서 최대한 풀어보려고 시도하였다. 또한 문제가 잘 이해되지 않았다. 처음에 답이 두개인가?? 생각도 하고 질문 답변을 확인한 결과 조금 이해가 되었다. 어느덧 3시간 고민 후... 각 N 마다 먼저 풀어야하는 문제를 우선순위 큐에 넣어 DFS 탐색까지 도달였다. 하지만 결과는 DFS로는 풀수 ..