https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제의 조건은 다음과 같다. N개의 자연수 중에서 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용도이다. 재귀함수에서 중요한 것은 종료조건이다. 여기서의 종료조건은 M개를 다 뽑았을 때이다. 그때 배열에 저장한 수를 모두 출력하면 된다. visited: 해당 수를 사용했는지 안했는지 판별하는..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제의 조건은 다음과 같다. N개의 자연수 중에서 M개를 고른 수열 앞의 N과 M 문제와 달라진 점은 입력으로 N개의 수가 주어진다는 것이다. 재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용도이다. 재귀함수에서 중요한 것은 종료조건이다. 여기서의 종료조건은 M개를 다 뽑았을 때이다. 그때 배열에 저장한 수를 모두 출력하면 된다. visited..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제의 조건은 다음과 같다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. N과 M(2)와 N과 M(3) 문제의 조건을 합쳤다. 재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제의 조건은 다음과 같다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용도이다. 재귀함수에서 중요한 것은 종료조건이다. 여기서의 종료조건은 M개를 다 뽑았을 때이다. 그때 배열에 저장한 수를 모두 출력하면 된다. 이전의 N과 M 문제와 다른 조건은 같은 수를 중복해서..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제의 조건은 다음과 같다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 15650번 N과 M (1)에서 추가된 조건은 두 번째 조건이다. 재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용도이다. 재귀함수에서 중요한 것은 종료조건이다. 여기서의 종료조건은 M개를 다 뽑았을 때이다. 그때 배열에 저장한 수를..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 브루트포스 방법을 사용하여 뽑기 문제를 풀 때 유형은 두 가지로 나뉜다. 1. 순서: N개 중에서 M개를 뽑을 때, 순서를 고려하는 경우 2. 선택: N개 중에서 M개를 뽑을 때, 순서를 고려하지 않는 경우 이 문제는 순서를 고려하지 않는다. 재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용도이다. 재귀함수에서 중요한 것은 종료조건이다. 여기서의 종료조건..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이 문제 또한 그냥 다 해보면 된다. 나올 수 있는 폴리오미노는 대칭과 회전을 허용하므로 총 19개이다. 따라서 이 19가지의 경우의 수를 모두 확인하여 가장 큰 값을 출력하면 된다. 참고로 이 문제는 정말... 집중해서 풀어야한다. 문제가 어렵다기보다는 디버깅이 매우 힘들기 때문이다. 이 문제에서는 오류를 찾는 것이 매우 힘들기 때문에 처음에 코드를 작성할 때 최대한 집중해서 작성하는 것이 좋다. import..

www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 숫자버튼을 누르고, 그 다음 +나 -중 하나만 연속해서 눌러야한다. 이 때, 숫자버튼을 눌러 가야하는 채널을 정해야하는데 이때 브루트포스 방법으로 구현하면 된다. 1. 이동할 채널 C를 정한다. 2. C에 포함되어 있는 숫자 중에 고장난 버튼이 있는지 확인한다. - 수를 10으로 계속해서 나누면서 하나씩 검사 3. 고장난 버튼이 포함되어 있지 않다면 |C-N|을 계산해 +나 -버튼을 몇 번 눌러..

www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net E, S, M 의 범위는 $ 1\leq E \leq15, 1\leq S \leq28, 1\leq M \leq19$으로 나올 수 있는 모든 경우의 수는 15 * 28 * 19 = 7980이다. 이 수는 큰 수가 아니므로 완전탐색의 방법을 이용하여 풀 수 있다. 1 에서 부터 1씩 증가시키면서 주어진 수와 같아질 때까지 비교했다. import sys input=sys.stdin.readline E, S, M = map(..

www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 처음에는 이 문제를 어떻게 풀어야할지 감이 안잡혔는데, 그냥 다 해보면 되는 거였다! 😀 그 이유는 테이블 크기가 50보다 작기 때문이다. 밑에 코드는 시간복잡도가 $O(N^4)$지만 애초에 테이블 크기가 작기 때문에 시간 초과가 나지 않는다. 인접한 두 칸을 고르고 사탕을 교환하는 방법은 상하좌우로 4가지가 있다. 그러나 테이블을 순차적으로 검사했을때, 위로 바꾸는 방법과, 왼쪽으로 바꾸는 방법은 이전에 검사했었으므로 다시 고려할 필요가 없다. 그러므로 밑으로 바꾸는 방법과, 오른쪽으로 바꾸는 방법 두 가지만 고려하면 된다. import..