분류 전체보기
-
백준(BOJ) 1965번 상자넣기알고리즘 풀이/백준(Boj) 2019. 7. 7. 01:42
문제 : https://www.acmicpc.net/problem/1965 입력파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.출력첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다. 나의풀이: LIS와 동일 코드 ( C ++ ) #include #include #include const int MAX = 1000;int line[MAX];int cache[MAX];int N;using namespace std;int findLongLength(int begin){int& ret = cache[begin];if (ret != -1)return ret;ret = 1;..
-
삼각형 위의 최대 경로 수 세기알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 7. 00:23
문제 : https://algospot.com/judge/problem/read/TRIPATHCNT 코드 ( C ++ ) 종만북 참조 #include #include using namespace std;const int MAX = 100+1;int N;int triangle[MAX][MAX];int path[MAX][MAX];int cache[MAX][MAX]; int count(int y, int x){if (y == N - 1) return 1;int& ret = cache[y][x];if (ret != -1)return ret;ret = 0;if (path[y + 1][x + 1] >= path[y + 1][x]) ret += count(y + 1, x + 1);if (path[y + 1][x + ..
-
백준(BOJ) 11727번 2xn 타일링 2알고리즘 풀이/백준(Boj) 2019. 7. 6. 03:07
문제 : https://www.acmicpc.net/problem/11727 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 나의 풀이: 2xn 타일링 문제 ( https://100100e.tistory.com/24 ) 와 거의 동일했다. 다른 점은 2x2 타일이 추가 된 것인데 마찬가지로 타일을 어떻게 덮었는지는 상관이 없다. 따라서 n-2를 채우는 방법이 2x2 타일을 쓰는 것과 2*1타일 두개를 가로로 배치한 두가지 방법이 될 것 . 따라서 tiling(n-2) 에 2배를 곱해주면 된다. 코드 ( C + + ) #include #include using namespace std;int N;co..
-
백준(BOJ) 11726번 2xn 타일링알고리즘 풀이/백준(Boj) 2019. 7. 6. 02:45
문제 : https://www.acmicpc.net/problem/11726 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 나의풀이 : 세로줄 왼쪽부터 채워나갈수 있는 경우의 수를 생각해보자. 세로로 한개, 가로로 두개 두 경우 이외에는 없기 때문에재귀적으로 구현해주고 n이 1000까지 있기에 완전 탐색으로는 시간 내에 불가능하니 메모이제이션을 적용해서 중복되는 탐색을 방지하자. 코드 ( C ++ ) #include #include using namespace std;int N;const int MAX = 1000;int cache[MAX+1]; // n이 1000일 경우 cache[1000]이 ..
-
백준(BOJ) 1302번 베스트셀러알고리즘 풀이/백준(Boj) 2019. 7. 6. 00:44
#include #include #include #include using namespace std; 문제: https://www.acmicpc.net/problem/1302 입력첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.출력첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다. 나의풀이 : pair vector에 책이름과 판매수를 적고 판매수를 기준으로 오름차순 정렬한다. 정렬된 list에서 제일 가장 많이 팔린 중복된 책들만 모..
-
백준(BOJ) 1182번 부분수열의 합알고리즘 풀이/백준(Boj) 2019. 7. 5. 01:35
문제: https://www.acmicpc.net/problem/1182 문제N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 코드 ( C++) #include using namespace std;int N, S;const int MAX = 20;int arr[MAX];int cnt; void find(int sum, int n){if (n == N) { // n이 N이 된..
-
백준(BOJ) 11048번 이동하기알고리즘 풀이/백준(Boj) 2019. 7. 3. 22:16
문제: https://www.acmicpc.net/problem/11048 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.출력첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다. 나의풀이 :완전탐색의 경우 탐색했던 경로를 또 탐색해야 하니 시간초과가 되었고 따라서 각 부분 문제를 최적으로 풀고 그 결과를 cache에 저장해 둠으로써 경로의 중복을 없앴다. 완전탐색 #include #include using namespace std;const int MAX = ..