https://www.acmicpc.net/problem/1965문제정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하..
Koala - 15기/코딩테스트 준비 스터디
풀이#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin.tie(NULL); int T; cin >> T; while(T--) { int n; cin >> n; int sticker_value[2][n]; for( int i = 0; i for( int j = 0; j > sticker_value[i][j]; } for( int i = 1; i if( i == 1 ) { sticker_va..
1932번: 정수 삼각형 (acmicpc.net)n = int(input())li= [list(map(int, input().split())) for _ in range(n)] for i in range(1,n): for a in range(len(li[i])): if a == 0: li[i][a]+=li[i-1][a] elif a == i: li[i][a]+=li[i-1][a-1] else: li[i][a]+=max(li[i-1][a], li[i-1][a-1])print(max(li[n-1]))처음칸은 안 변하니 다음 칸부터 본다. li에 더한 값을 저장할 것이다. 해당 열을 모두 보는데 첫 번쨰..
https://www.acmicpc.net/problem/11053 bottomup방식으로 풀었다.구하고자 하는 것은 증가하는 부분수열의 길이중 가장 긴 길이이므로 배열에 수를 일단 입력받고dp배열을 하나 더 만들어 해당 인덱스마다 인덱스까지의 최장증가부분수열의 길이를 넣어주었다.넣어줄 때 중요한 규칙은오름차순이어야하니 현재인덱스가 담고 있는 수보다 작은 수여야하고, 작은 수들마다 각각의 dp값을 갖고 있으니 그 중에서 가장 긴 값에 +1을 해준값을 현재 인덱스에 넣어주면 된다. import java.io.*;import java.util.*;public class Main { static int dp[]; static int arr[]; static BufferedWriter bw =..
https://www.acmicpc.net/problem/1463 문제풀이import sysdef cnt(N): if N 9를 입력하면 9 -> 3 -> 1 이 될것이다. 기존 값을 3 또는 2로 나누고 count 를 1씩 증가시키는 형태이다. 3의 배수이면 3 나머지 2의 배수이면 2로 나눈 나머지 값이 0임을 판단하여 배수임을 확인한다. 둘다 아닐경우 빼는 경우이다. 점화식을 세우면 dp[i] = 1 + dp[i // 3] 또는 dp[i] = 1 + dp[i // 2] 그리고 dp[i] = 1 + dp[i - 1] 가 될것이다. 3가지 경우로 구분하고 3또는 2로 나눌때 1을 뺀 값과 비교하여 어떤값이 최솟값인지 구분하여 저장한다. 3과 2의 공배수인 6의 경우 3으로 나눌때와 2로 나눌때 어..
https://www.acmicpc.net/problem/1912문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입출력풀이수열을 순회하면서 이전까지의 최대합을 기록해두고 이를 통해 이번 위치에서..
https://www.acmicpc.net/problem/14405 문제길이가 5000이 넘지 않는 알파벳 소문자로 이루어진 문자열 S를 입력받고, S가 "pi", "ka", "chu"로만 이루어져 있는 경우 "YES", 그렇지 않은 경우 "NO"를 출력한다. 풀이문자열을 입력받고, 인덱스를 기준으로 2, 3개씩 문자열을 잘라서 비교하며 조건을 만족하는지 확인한다.#include #include using namespace std;string s, ans = "YES";int main() { cin >> s; int idx = 0; while (idx
https://www.acmicpc.net/problem/1038문제음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.입력첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력첫째 줄에 N번째 감소하는 수를 출력한다.예제 입출력풀이문제 조건에 입이 1,000,000보다 작은 수임이 제시되었기 때문에 dfs를 이용해 감소하는 수를 모두 찾고 이를 정렬해 정답을 찾아내는 방식..
15652번: N과 M (4) (acmicpc.net)중복이 가능한 조합을 찾는 코드조합이므로 자신이 포함된, (그 앞은 포함되지 않은) 식의 구분을 지어줘야함# 중복 조합n, m = map(int, input().split())arr = [0 for i in range(m)]def recur(cur, start): if cur == m: print(*arr) return for i in range(start, n): arr[cur] = i+1 recur(cur+1, i) recur(0, 0)
https://www.acmicpc.net/problem/25602문제랑이 집사는 자신의 고양이 랑이와 메리 둘에게 매일 아침 캔을 정확히 하나씩 준다. 랑이 집사가 가진 캔의 종류는 N가지로, 집사는 i번째 캔을 A[i]개 갖고 있다. 랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다. i번째 날 랑이가 j번째 캔을 먹었을 때 만족도는 R[i][j], i번째 날 메리가 j번째 캔을 먹었을 때 만족도는 M[i][j]로 나타난다. 자연수 N과 A, R, M 배열이 주어질 때, 랑이 집사가 현재 가진 캔으로 K일동안 랑이와 메리에게 하루에 하나의 캔을 줘서 얻을 수 있는 만족도의 합의 최댓값을 구하는 프로그램을 작성하시오.입력 & 출력첫째 줄에 N, K가 주어진다. (1 ..
https://www.acmicpc.net/problem/9095문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 소스코드def go(arr): global cnt if sum(arr) == n: cnt += 1 ..
풀이#include #define MAX 1000001 #define MOD 1000000009 int n; long long d[MAX]; using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; d[1] = 1, d[2] = 2, d[3] = 4; while(T--) { cin >> n; for( int j = 4; j d[j] = (d[j - 3] + d[j - 2] + d[j - 1]) % MOD; } cout } ..
