본문 바로가기
반응형

분류 전체보기151

백준 1759 암호 만들기 - C++ 접근 이전에 풀었던 N과 M 문제와 매우 유사하다 다만 조건이 모음과 자음의 개수에 따라 결과가 달라지는 것 정도 우선, 위에 보이는 출력 처럼 문자를 오름차순으로 보여주려면 입력 받은 값에 대해 정렬을 하고 시작하면 빠르다. 입력된 문자가 정렬 되었다면 이제 조건에 만족하는 경우의 수를 구해준다. * 조건은 중복 없이 오름차순이고 만들어진 문자열은 모음 1개 이상 자음 2개 이상을 포함한다. #include #include #include using namespace std; map vowel; int L, C; char alpha[15]; char arr[15]; void re(int idx, int begin, int vowelCnt){ if(idx == L){ int consonant = L-vo.. 2020. 7. 17.
백준 9095 1, 2, 3 더하기 - C++ 접근 해당 문제는 DP로 푸는 방법과 모든 경우의 수를 구해서 푸는 방법이 있다. 먼저, DP로 푸는 방법은 다음과 같다. 해당 문제는 어떠한 N을 1,2,3의 합으로만 구해야 한다. N은 4이상이고 10이하의 경우 N은 N-1의 경우의 수 +1, N-2의 경우의 수 +2, N-3의 경우의 수 +3을 하게 되면 N이 가질 수 있는 경우의 수가 나오게 된다. 즉 N이 가질 수 있는 경우의 수는 (N-1의 경우의 수) + (N-2의 경우의 수) + (N-3의 경우의 수) 가 된다. 코드는 다음과 같다. #include using namespace std; int dp[11]; int main(){ int total; cin >> total; dp[1]=1, dp[2]=2, dp[3]=4; while(tota.. 2020. 7. 16.
Level2. 프로그래머스 땅따먹기 - JavaScript 접근 처음에는 각 행에서 제일 큰 값만 취한다면 결국 제일 큰 값이 나올 것이다. 라고 생각했지만 이전 행에서 선택한 열은 이번 행에서 선택은 못하기 때문에 예외 사항이 생길 수 있다. 예를 들어 [ [1,2,3,4], [3,4,5,9], ] 다음과 같은 입력이 주어지고 각 행에서 제일 큰 값을 선택 한다고 했을 때 첫 번째 행에서 제일 큰 값 4를 선택하고 아래 행에서 같은 열인 9는 선택 못하고 그 다음 큰 값인 5를 선택해 9가 된다. 하지만 첫 번째 행에서 3을 선택하고 다음행에서 9를 선택한다면 최종값이 12가 된다. 따라서 다른 방법을 써야한다. 두 번째로 완전탐색을 생각해보았다. 구할 수 있는 모든 경우의 수에서 최종값이 가장 크다면 그게 정답일 것이다. 하지만 해당 문제의 N의 최대값은 1.. 2020. 7. 16.
백준 15663 N과 M(9) - C++ 전체적인 흐름 주어진 N에 대해서 입력 받은 배열을 오름차순으로 정렬한다.(사전 순으로 증가하는 순서로 출력하기 위해) N개 있는 배열에서 M개를 뽑아 만들 수 있는 경우의 수를 모두 구한다. 여기서 이전에 사용한 수는 사용하면 안되며 똑같은 수열을 만드는 경우는 피해야 한다. 예제 만약 1 1 3 4 5 라는 입력이 있다고 했을 때 이번 문제에서 요구하는 출력은 1 1 1 3 1 4 1 5 3 1 3 4 3 5 4 1 4 3 4 5 5 1 5 3 5 4 이다. 배열 인덱스 0과 1에서 1 1이 존재하는데 경우의 수를 구하다 보면 1 1이 나오고 또 1 1이 나오는데 두 개는 같은 의미이므로 같은 수열이 나온다면 하나만 출력해주면 된다. 풀이 그래서 이것을 똑같은 수열이 나오는지 어떻게 판별할 것인가를 .. 2020. 7. 14.

티스토리툴바