문제 링크16987 계란으로 계란치기 접근 및 알고리즘문제를 이해하는 것만 해도 시간이 들었다. 나의 집중력 이슈 ㅜㅜ문제 내용을 요약하자면 다음과 같다.1. 입력으로 받은 계란 중 첫번째 계란을 손에 쥔다.2. 남은 계란 중에 하나를 손에 쥔 계란으로 친다. (손에 든 계란이 깨졌거나, 현재 계란 말고 다른 계란이 전부 깨져 있으면 치지 않는다.)3. 이때, 손에 있는 계란이 깨질 수도 있고, 다른 계란이 깨질 수도 있고, 둘 다 깨질 수도 있다.4. 아무튼 손에 있는 계란이 깨졌든 말든 한번 쳤으면 손에 있는 계란을 다시 제자리에 놓는다.5. 그 다음에, 손에 있었던 계란의 다음 차례 계란을 손에 쥔다.6. 2 - 5를 반복하고, 만약 방금 손에 쥐었던 계란이 마지막 위치의 계란이면 종료한다. 첫번째..
문제 링크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번째 수를 뽑기 위해 재귀 함수를 실행한다. 이때,..
문제 링크N과 M (8) N과 M 시리즈를 풀면서 뭔가 계속 날먹하고 있는 기분이다...큰 틀은 똑같고 부분부분 조건만 바꿔주면 되는 문제이다 보니...약간 공부를 안 하는(?) 느낌이다.아무튼 점수 올리고 개꿀. ㅎㅎ 문제 해석N개의 자연수 중 M개를 뽑는다. 이때 수는 중복으로 뽑아도 되지만 다른 수열과 순서는 같으면 안된다. 또한 내림차순 수열은 불가능하다. 접근백트래킹을 이용하여 풀었다.이때 중복은 허용하고, 내림차순 수열을 방지하기 위해 조건을 하나 붙였다.아까 뽑았던 숫자가 지금 뽑을 숫자보다 크면, 이 수열은 내림차순 수열이 되므로 pass 한다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장..
문제 링크15656 N과 M (7) 접근N개의 수 중에서 M개를 뽑아 만들 수 있는 수열을 모두 만드는 문제이다. 이때, 같은 수를 여러 번 골라도 되지만 순서는 달라야 한다. 따라서 백트래킹을 이용해 모든 경우의 수를 찾아 주었다. 그리고 사전순으로 출력해야 하기 때문에 사전에 배열을 sort 해 주었다. 코드#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 > N >> M; for (int ..
