https://www.acmicpc.net/problem/1965문제정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하..
분류 전체보기
풀이#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..
https://www.acmicpc.net/problem/2511문제풀이a = list(map(int,input().split()))b = list(map(int,input().split()))score=[0,0]str ="D"for i in range(10): if a[i]>b[i]: score[0]+=3 str = "A" elif a[i]score[1]: print('A')elif score[1]>score[0]: print('B')else: print(str)설명1. 점수가 동점이어도 마지막 승자가 승리한다. 즉 비기는 경우는 모든 판이 무승부인 경우2. 마지막에 이긴 사람이 누구인지를 str에 초기화 시킨다. 이때 처음에 "D"로 무승부인 경우를..
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/1152영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.입력첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다.출력첫째 줄에 단어의 개수를 출력한다.풀이여태까지 우리가 배운 내용을 결합한 간단한 문제이다.문장을 공백을 기준으로 각각 나누어 리스트의 형식으로 저장한 뒤,리스트의 길이를 출력하면 된다.이를 잘 사용하면 한 ..
문제 https://www.acmicpc.net/problem/17212 Algorithm토끼는 1,2,5,7원의 동전을 가지고 최소의 개수로 해당 가격을 딱 맞추어서 내야한다.예를 들어 23원이라고 해보자. 23원을 완성하는 경우의 수는 여러가지가 있지만 이를23 = 7 + 16원을 만들기 위한 동전개수 = 5 + 18원을 만들기 위한 동전개수 = 2 + 21원을 만들기 위한 동전개수 = 22 + 1원을 만들기 위한 동전 개수가 된다. 즉 N(N>7)원에 대하여 N원을 지불하기 위해 필요한 최소 동전 개수는 min(N-1, N-2. N-5, N-7) + 1개이다.dp배열을 만들고, dp[0] = 0로 기준을 잡아서 반복문을 돌린다.해당 가격에 대해 1,2,5,7원을 뺀 값의 동전 개수를 확인하여 이중에..
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/10773문제문제풀이정수를 K번 입력받는다. K번 정수를 입력받는 동안 정수가 "0"일 경우에는 pop()을 이용해서 정수를 저장한 리스트의 가장 마지막 값을 지운다. 정수가 "0"이 아닌 경우에는 append()를 이용해서 정수를 저장한 리스트에 값을 추가한다.sum()을 이용해서 정수를 저장한 리스트에 있는 원소들의 합을 출력한다.소스코드K = int(input())nList = []for i in range(K): n = int(input()) if n == 0: nList.pop() else: nList.append(n)print(sum(nList))
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/11652 풀이!! 범위를 고려하여 long long int 자료형을 사용하여야 함 !! 1. map 자료구조를 사용하여 입력받을 카드의 숫자를 키, 해당 카드가 나온 횟수를 값으로 가지도록 한다. * map 자료구조의 특징으로는 키와 값을 쌍으로 가진다는 것, 레드-블랙 트리(균형 이진 트리)를 사용하여 키를 오름차순으로 정렬하여 관리한다는 것, 중복 키를 허용하지 않는다는 것 등이 있다.2. 입력받은 숫자를 map 자료구조에 삽입하고 해당 키와 쌍으로 이루어진 값을 1 증가시킨다.3. auto를 이용해서 map을 순회한 후, 최빈값을 찾아낸다.* auto는 변수의 타입을 자동으로 추론하여 선언할 수 있게 해주는 기능으로, 이 문..
문제 & 링크https://www.acmicpc.net/problem/1673 풀이!! 치킨 쿠폰과 도장을 잘 구분해야 함 !!도장 k개 -> 치킨 쿠폰 1개 -> 치킨 한 마리 주문 -> 도장 1 1. 몇 줄을 입력받을지 모르기에 EOF (End Of File) 조건을 이용하여 while문을 만들고 입력받는다. 입력을 종료하면 cin 객체의 상태가 false가 되며 반복문을 탈출한다.2. ans(정답), stamp(도장), coupon(쿠폰)을 각각 0, 0, n으로 초기화한다.3. 쿠폰의 개수만큼 정답 및 도장의 개수를 늘린다. (이때 쿠폰은 모두 사용)4. 도장을 k로 나누어 해당 몫 만큼 쿠폰을 생성하고, 나머지 개수를 저장한다.5. 3 - 4의 과정을 쿠폰이 0개가 될 때 까지 반복한다. 코드..
