[Baekjoon]백준 1182번 부분수열의 합 1182번 부분수열의합 문제 풀이문제N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절대값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.예제입력5 0 -7 -3 -2 5 8 출력1해결방법재귀함수를 사용하여 모든 원소들에 대한 부분집합을 전부 만들어 본 후에 입력한 값이랑 같은지 비교하는 방법을 사용했다.변수&함수내용num정수의 개수result구해야할 정수a원소를 저장시..
[Baekjoon]백준 6603번 로또 6603번 로또 문제 풀이문제독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 입력의 마지막 줄에는 0이 하나 주어진다.출력각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.예제입력 7 1 2 3 4 5 6 70출력1 2 3 4 5 61 2 3 4 5..
[Baekjoon]백준 10971번 외판원순회2 10971번 외판원 순회2 문제 풀이문제1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 어느 한 도시에서 출발하여 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단 한 번 갔던 도시로는 갈 수 없다. 각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어지며 도시 i에서 도시 j로 가기위한 비용을 나타낸다. 갈 수 없는 도시 및 자기자신은 항상 0이된다. 가장 적은 비용을 들이는 여행 계획을 세워라.입력첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진..
[Baekjoon]백준 9095번 1,2,3더하기 9095번 1,2,3더하기 문제 풀이문제정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.'4' 입력 시 나타낼 수 있는 방법 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.예제입력34710출력 744274해결방법브루트포스가 아닌 DP를 활용하면 쉽게 해결할 수 있으나 이 카테고리에서는 브루트포스로 해결해보려고 한다.plus_1이라는 재귀함수를 통하여 더해지는 마지막 인자 값이 1이 될 때 ..
썸네일 [Baekjoon]백준 14500번 테트로미노 14500번 테트로미노 문제 풀이문제폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안된다.도형은 모두 연결되어 있어야 한다.정사각형의 꼭짓점끼리 연결되어 있어야 한다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.입력첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 50..
[Baekjoon]백준 1476번 날짜계산 1476번 날짜계산 문제 풀이문제준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.입력첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.출력첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이..

티스토리툴바