문제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/15652시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이 역시 백트래킹 문제이다. 다만 이전에 풀었던 15650번 N과 M(2)과 비슷한 문제이다. 비내림차순이라는 단어가 나와서 내림차순이 아닌 상태의 수열을 출력하라는줄 알고 순간 놀랐지만, 오름차순이라는 말을 굳이 꼬아서 쓴 것이었다. 해당 문제는 중복을 허용하기 때문에 15650번과는 다르게 반복문의 범위를 이전에 선택한 값도 다시 선택할 수 있도록 했다.코드#include #define endl '\n'using namespace std;int n, m;void sol(int prev, int cnt, string output) { if (cnt == m) { cout..
문제https://www.acmicpc.net/problem/15650 시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이이 문제를 무작정 중첩반복문으로 풀기에는 어려워보인다. 중첩반복문을 쓰게되면 시간복잡도의 문제도 생기지만, 그 전에 몇번 중첩해야할지가 애매해진다. 숫자를 M개를 선택해야하는데, 이는 단순하게 생각해서 M중첩 반복문이 필요하다는 뜻이 될테니 말이다. 따라서 반복문만 사용하는 것이 아닌, 재귀함수와 섞어, 어떤 숫자를 선택했을때, 그 뒤의 숫자부터 다시 탐색하도록 작성하였다. 그러기 위해 제일 최근에 선택한 숫자가 무엇인지, 지금 몇개를 선택했는지를 재귀하면서 넘겨주고, 항상 이전에 선택한 숫자보다 더 큰 숫자부터 다시 탐색을 하는 방식을 선택하였다. 답을 출력하기 용이하..
