문제 링크18808 스티커 붙이기접근최대한 문제에서 제시한 대로 구현하려고 노력했다. 그러나 답은 맞았지만 머릿속에서 꼬여버린 탓에 코드를 덕지덕지 짠 것 같다. 그래서 시간복잡도가 그렇게 좋지 못한 결과가 나왔다. 그래서 바킹독님 블로그에 제시된 간결한 코드로 다시 복습해 보려 한다. 앞으로는 먼저 계획을 세우고 코드를 짜는 습관을 길러야겠다. 알고리즘노트북에 스티커를 붙일 수 있는지 확인한다.만약, 스티커를 붙일 수 있다면 스티커를 붙인다.만약, 스티커를 붙일 수 없다면 스티커를 회전한다.모든 방향으로 회전하여도 스티커를 붙일 수 없다면 그 스티커를 버린다.이를 스티커를 다 쓸 때까지 반복한다.코드#include using namespace std;int n, m, k;int note[42][42];..
문제 링크1759 암호 만들기접근조건을 만족하는 모든 경우의 수를 찾는 문제이므로 백트래킹을 사용하여 풀이하였다. 알고리즘k번째 문자를 뽑기 위해 다음과 같은 절차를 거친다. 만약 지금 뽑을 문자가 이미 사용되었다면, continue만약 지금 뽑을 문자가 이전에 뽑은 문자보다 사전순으로 앞에 있다면, continue (증가하는 순서로 배열되어야 하기 때문) 문자를 뽑는다. 만약 이 문자가 모음이라면, 모음 개수를 +만약 이 문자가 자음이라면, 자음 개수를 + 여기까지 왔다면, 문자가 사용된 것도 아니고, 사전순에 위반하는 문자도 아니므로 문자를 확정해 준다.이후 사용했다고 중복 배열에 표시. 다음, k + 1 번째 문자를 뽑기 위해 재귀함수를 실행한다. 이렇게 진행하다가 필요한 모든 문자를 다 뽑았다면,..
문제 링크15666 N과 M (12)풀이N과 M (11) 문제 풀이에서 비내림차 수열만 방지하면 되는 문제이다. 따라서 조건문에 비내림차 수열을 방지하는 조건을 추가하여 문제를 풀이하였다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int picked[10];// 숫자 모음int numbers[10];// k 번째로 저장할 수를 탐색 void Solve(int k){ if (k == M) { for (int i = 0; i 0 && picked[k - 1] > numbers[i])) continue; picked[k] = numbers[i]; tmp = p..
문제 링크15665 N과 M (11)풀이N개의 수 중 M개를 뽑아 수열을 사전순 증가로 출력하는 문제이다.이때, 수는 중복해서 뽑아도 되지만, 중복되는 수열은 만들면 안 된다. 예N개의 수가 [1 ,7, 9(A), 9(B)]일 때.(1, 1), (9(A), 9(A)) ------> 가능 But (9(A), 9(A))가 먼저 뽑혔으므로 (9(A), 9(B))는 불가능.(1, 7), (7, 1) -------------> 가능(1, 9(A)), (1, 9(B)) -----> 불가능 따라서 N과 M(9) 문제 풀이에서, 중복된 수를 허용하는 부분만 추가해 주면 되기 때문에 isUsed 배열과 조건문을 삭제하여 해결하였다.코드#include #include using namespace std;// N개 중..
문제 링크15664 N과 M (10) 접근N개의 자연수 중, M개의 수를 뽑아 비내림차 수열을 만드는 문제이다.이때 N개의 자연수는 (4, 4, 2)와 같이 중복된 숫자가 들어갈 수 있다. 예제 입력4 29 7 9 1 예제 출력1 71 97 99 9 위의 예제와 같이 (1, 7)이 뽑히면 추후 (7, 1)은 뽑을 수 없다.따라서 N과 M(9)번 문제의 풀이에서 조건을 추가하여 문제를 풀었다.조건 추가(1, 7), (7, 1)과 같은 중복을 막기 위해 뽑을 수열을 (k-1번째 수, k번째 수)이라고 가정했을 때, k-1번째 수 > k번째 수이면 백트래킹을 하지 않고 패스한다. 코드#include #include #include using namespace std;// N개 중에서, M개 뽑음int N, M..
문제 링크15663 N과 M (9)접근N개의 수 중 M개의 수를 뽑아 수열을 만든다. 이때, 중복되는 수열은 없어야 하며, 사전순으로 출력해야 한다.예를 들어, 4개의 수(1, 7, 9(A), 9(B)) 중 2개를 뽑아 만들 수 있는 수열은 다음과 같다.1 71 97 17 99 19 79 9 (1, 7), (7, 1)은 되지만 (1, 9(A)), (1, 9(B))는 안 된다. 즉 사전순으로 중복되면 안 된다. 기존 백트래킹 방식에서 조금 응용하여 풀었다. 배열은 정렬되어 있다고 가정한다. N개의 수(1, 7, ... ,9(A), 9(B)) 중 M개를 뽑아 만들 수 있는 수열을 만든다고 가정해 보자. 기존 백트래킹 방식에서는 k번째 수를 뽑은 다음, k+1번째 수를 뽑기 위해 재귀 함수를 실행한다. 이때,..
