https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 어떤 날은 상담을 하는 것이 좋고, 어떤 날은 오히려 상담을 안하는 것이 좋다. 안하는 것이 좋은 날은 이후에 상담을 하게 되는 것이 수익이 더 많은 경우이다. 이것은 상황에 따라 그때그때 다르니 모두 해보는 것이 좋다. sum: day-1일까지의 수익 1. 상담을 한다: go(day+T[day], sum+P[day]) - 현재 날짜에서 상담을 할 경우 걸리는 날짜를 더해준다. - 현재까지 얻은 수익에서 상담을 할 경우 얻게 되는 수익을 더해준다. 2. 상담을 안한다: go(day+1, sum) - 상담을 안하고 다음날로 넘어가므로 ..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제의 조건은 다음과 같다. 암호의 길이는 L이다. 암호는 C 개의 알파벳으로만 이루어진다. 최소 한 개의 모음과 최소 두 개의 자음이 포함되어 있어야한다. 3번의 조건을 맞추기 위해 check를 만들었다. check 함수는 자음과 모음 갯수를 세서 3번 조건에 맞는지 확인하는 함수이다. import sys input = sys.stdin.readline def check(password): ja ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제의 조건은 간단하다. 숫자 n을 입력받고 1, 2, 3을 이용해 N을 만들 수 있는 경우의 수를 만들면 된다. 나는 이 문제를 두가지 방법으로 풀었다. 1. DP 테이블 활용 2. 재귀함수 활용 1. DP 테이블 활용 주어지는 N이 11보다 작은 수이기에 DP 테이블을 활용하여 충분히 풀 수 있을 것이라고 생각했다. DP[i]에는 1, 2, 3 으로 i를 만들 수 있는 경우의 수가 들어간다. 예를들어, 4를 1, 2, 3으로 만드는 경우의 수는 다음과 같다. 1+1+1+1 1+1+2 1+2+..

https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 앞서 풀었던 N과 M 문제의 심화 버전이다. N과 M문제는 1차원 배열이었다면, 이 문제는 2차원 배열이다. 그러나 풀고자 하는 원리는 같으므로 재귀를 통해 해결할 수 있다. 그러나 문제는 시간복잡도이다..🥲 시간을 줄이는 가장 좋은 방법은 중복해서 계산하는 값을 찾아내서 없애는 것이다. 이 문제에서는 go함수에서의 for문에서 중복 계산이 일어날 수 있다. 이를 해결하기 위해 (px,..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. import sys input = sys.stdin.readline def go(index, start, n, m): if index == m: print(' '.join(ma..

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제의 조건은 다음과 같다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 중복을 허용했으므로 visited 배열은 필요없다. arr: 입력받은 배열 result: 출력할 배열 import sys input = sys.stdin.readline def go(index, n, m): if index == m: print(' '.join(map(str, resu..

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 문제와 다른 조건은 같은 수를 중복해서..