문제https://www.acmicpc.net/problem/2230시간 제한메모리 제한solved.ac 티어2초128MB골드 5풀이 밀린 문제 정리하기. 이 문제는 두가지 풀이가 존재한다. 첫번째 풀이는 투포인터이고, 두번째 풀이는 이분탐색이다. 사실 이 문제를 예전에 풀었을때에는 투포인터로 풀어냈고, 정리하려고 문제를 다시 봤을때에는 이분탐색으로 풀어냈다. 우선, 문제를 읽어보고 알 수 있지만, 수열의 원소의 순서는 크게 중요하지 않다. 따라서, 정렬을 해주었다. 투포인터가 됐던, 이분탐색이 됐던 정렬을 해주는게 용이하기 때문이다. 투포인터 풀이는 l, r 포인터를 모두 0에 위치시킨다. 두 원소의 차이가 m 이하라면 r 포인터를 오른쪽으로 한칸 옮긴다. m보다 크다면 l포인터를 오른쪽으로 옮긴다..
문제https://www.acmicpc.net/problem/1036시간 제한메모리 제한solved.ac 티어2초128MB골드 2풀이 이 문제는 1339번을 풀어본 기억이 있어 쉽게 풀 수 있었다. 1339번 문제는 각 자릿수를 알파벳으로 바꾸고, n개의 숫자들을 더한 후, 알파벳에 숫자들을 매핑시켰을때의 최댓값을 구하는 문제이다. 자세한건, 문제 풀이한 글을 읽어보도록 하자. 백준 1339번 C++ 풀이https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있codejin.tistory.com 1339번 문제와 유사하게..
문제https://www.acmicpc.net/problem/2258시간 제한메모리 제한solved.ac 티어2초128MB골드 4풀이 이 문제를 풀면서 내가 자꾸 하는 실수를 되짚어보았다. 이 문제를 정리하면 임의의 고기의 가격 미만의 고기는 공짜로 얻을 수 있을 때, 원하는 고기의 양을 만들기 위한 최소비용을 구하는 문제이다. 구현에 문제는 거의 없었지만, 정말 많은 실수를 하면서 무수한 WA를 받았다... 변명이나 해보자면 전날 저녁도 제대로 못먹고, 3시간 반정도 자고 일어나자마자 문제를 풀고 있지만... 사실 지금까지 비슷한 실수(물론 이쯤되면 실수라고 하면 안될거 같다)를 여러번 해왔기 때문에 항상 주의해야할 것 같다. 문제를 보자마자, "아 이거 정렬하고 무게 누적합해가면서 최소가격 찾으면 ..
문제https://www.acmicpc.net/problem/7453시간 제한메모리 제한solved.ac 티어12초1024MB골드 2풀이 이 문제는 단순무식한 문제이지만, 그래도 배울만한 점이 꽤 있는 문제이다. 시간제한이 12초라는 듣도보도 못한 엄청난 수치에 그래도 배열 길이가 4천밖에 안되기 때문에 완탐을 하는게 아니고선 어지간해서 통과될거라 생각했다. 문제를 보자마자 떠올린 풀이는, a배열과 b배열, c배열과 d배열의 각 원소의 합을 저장한 원소를 ab, cd배열이라고 하자. ab배열과 cd배열에는 중복되는 원소가 존재할 수도 있고 아닐수도 있다. 그렇기에 unordered_map에 원소와, 해당 원소가 등장하는 횟수를 기록한다. unordered_map은 해시이기에 평균적으로 탐색에 O(1)이다..
문제https://www.acmicpc.net/problem/15663시간 제한메모리 제한solved.ac 티어1초512MB실버 2풀이 며칠만인지 모르겠지만 아무튼 오랜만에 밀린 문제 정리하기다. 이번 N과 M은 원소를 조합으로 뽑는 문제이다. 언제나 그렇듯 사전 기준 오름차순 출력이기 때문에 입력받은 N개의 원소를 정렬한 후, 백트래킹으로 M개의 숫자를 중복없이(같은 인덱스의 원소를 뽑지 않고) 뽑는다. 이때 N개의 원소에는 중복되는 원소가 존재할 수 있다. 이를 모두 고르게 되면 중복되는 수열이 등장하게 된다. 이를 방지하기 위해 map에 출력한 output과 해당 값이 출력되었는지 기록하여, 중복된 수열이 나오더라도 출력은 한번만 되도록 했다.코드#include #define ALL(X) X.be..
문제https://www.acmicpc.net/problem/1759시간 제한메모리 제한solved.ac 티어2초128MB골드 5풀이 문제를 읽어보면 정말 익숙한 그 냄새가 난다. N과 M 문제의 냄새가 말이다. 따라서 이 문제는 백트래킹이다. 물론 문자의 개수가 많지 않고 시간제한이 2초나 되기 때문에 입력받은 문자를 자음과 모음으로 나누어 일일이 브루트포스를 해도 답은 맞을 것 같다. 처음 문제를 풀고나선 WA를 받았는데, 자음 조건을 놓쳐서 틀렸다. 이런 실수는 줄여나가야 하는데 말이다...코드#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespace std;int l, c;string pwd, vowels, consona..
문제https://www.acmicpc.net/problem/25955시간 제한메모리 제한solved.ac 티어1초512MB실버 4풀이 오늘은 개인적으로 일이 바빠서 실버문제 한문제만 풀고 정리하려고 한다. 정렬문제이다. 랜덤으로 뽑았는데 이게 나왔다. 정렬되어있지 않은 두개의 값을 찾는 문제이다. 원소의 개수도 많지 않고, 찾아야 하는 원소도 두개뿐이니, 정렬한 다음에 같은 인덱스의 다른 원소 둘을 찾아 출력하면 된다. 코드#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespace std;int n;vector diff;string symbol = "BSGPD";void input() { cin >> n; diff.resize..
문제 시간 제한메모리 제한solved.ac 티어2초256MB골드 4풀이이 문제도 밀린 문제이다. 언제 정리 다하나... 각설하고, 풀이를 해보겠다. 2467번이자 2470번 문제인 두 용액 문제(https://codejin.tistory.com/270)와 매우 유사한 문제이다. 해당 문제에서는 두 수의 합의 최솟값을 찾는 문제였지만, 이번 문제는 두 수의 합이 해당 배열에 존재하는지 여부를 따지는 문제이다. 유의할 점은 배열에 값이 같더라도 다른 값으로 본다는 점이다. 배열에 10이 두개 있고, 다른 두수의 합으로 10을 만들 수 있다면 이 두개 모두 좋은수이기 때문에 개수를 2개 올려줘야 한다. 입력받은 배열을 선형 탐색하면서, 원소 하나를 선택 한 후, 투포인터를 통해 해당 값을 만들 수 있는지 따져..
