문제 개요문제 링크 : https://www.acmicpc.net/problem/2839 위 문제를 쉽게 얘기하면 우리는 설탕 배달을 맡은 배달원입니다.설탕을 포장할 수 있는 봉지는 딱 두 종류 뿐입니다.5kg 봉지3kg 봉지이제 고객이 N kg의 설탕을 주문했습니다.당신은 이 설탕을 최대한 적은 수의 봉지로 포장해야 합니다. 만약 정확히 N kg을 만들 수 없다면?-1을 출력하세요. 예를 들어 입력이18 이렇게 들어왔으면총 설탕 18kg을 배달해야 함가능한 포장 방법5kg x 3개 = 15kg나머지 3kg → 3kg x 1개총 4봉지가 나오게 됩니다.이걸 직접 풀어보면 다음과 같습니다.배달원설탕 (kg)포장 봉지 (kg)남은 설탕 (kg)118518 - 5 = 13213513 - 5 = 83858 - ..

문제 개요문제 링크 : https://www.acmicpc.net/problem/11399 위 문제를 쉽게 얘기하면 ATM 앞에 사람들이 줄을 서 있습니다.각 사람은 돈을 인출하는데 걸리는 시간이 모두 다릅니다.이제 줄을 어떻게 세울지를 우리가 정할 수 있습니다.누가 먼저 인출할지 정해서, 모든 사람이 기다리는 시간의 총합을 최소화 해야하는 문제입니다. 예를 들어 입력이53 1 4 3 2 이렇게 들어왔으면사람 수 : 5명각 사람이 인출하는데 걸리는 시간 : [3, 1, 4, 3, 2]이걸 직접 풀어보면 다음과 같습니다.사람인출시간대기시간누적합1300 + 3 = 32133 + 1 = 43444 + 4 = 84388 + 3 = 11521111 + 2 = 13 총 대기 시간의 합은 3 + 4 + 8 + 1..

문제 개요문제 링크: https://www.acmicpc.net/problem/11047 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있습니다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하는 문제입니다. 더 쉽게 얘기하면 어떤 나라에는 동전이 N종류가 있고,각 동전은 가치는 서로 다르고, 단위가 클수록 더 값이 비싸다고 합니다.그리고 우리는 지금 K원을 만들려고 합니다. 가능한 한 적은 개수의 동전으로 K원을 만드는 것입니다. 예를 들어 입력이10 4200151050100500100050001000050000 입력을 해석해보면동전은 10종류 있음만들어야 하는 금액: 4200원사용할 수 있는 동전: [..

문제 개요문제 링크: https://www.acmicpc.net/problem/2869 문제를 설명하자면 어느 날 달팽이가 우물을 올라가기로 결심했습니다.하지만 이 우물의 높이는 V미터이고, 달팽이는 다음과 같은 규칙으로 이동합니다.낮에 A미터 올라감밤에 B미터 미끄러짐이 행동을 반복하면서, 달팽이는 언젠가 꼭대기에 도달하고 말 겁니다.여기서 질문은 이 달팽이는 며칠 만에 우물 꼭대기에 도달할까요? 예를 들어 입력이2 1 5 이 들어왔다면낮에 2미터 올라가고밤에 1미터 미끄러지고우물의 높이는 5미터라는 뜻입니다.진행과정을 자세하게 살펴보겠습니다.날짜아침에 올라감저녁에 미끄러짐위치1일차+2-112일차+2-123일차+2-134일차+2-145일차+2도착!6 그럼 최종적인 정답은 5일이 됩니다. 여기서 핵심은..

문제 개요문제 링크 : https://www.acmicpc.net/problem/2042 해당 문제를 요약해보면 숫자 N개가 있고, 다음 2가지 요청을 반복해서 처리해야하는 문제입니다. 예를 들어 우리는 지금 숫자 카드 N장을 가지고 있다고 가정을 하겠습니다.[1] [2] [3] [4] [5] 이제 다른 사람이 아래 처럼 계속 요청을 하는겁니다.3번째 카드 숫자를 6으로 바꿔주세요.2번째부터 5번째 카드 숫자를 모두 더해주세요.만일 요청이 수십만 번 이상 반복도리 경우 그냥 for문으로 처리한다면, 시간 초과가 날 가능성이 높습니다.그래서 빠르게 처리하는 방법이 필요합니다. 그걸 해결할 수 있는 방법이 세그먼트 트리입니다. 세그먼트 트리란?세그먼트 트리란?- 숫자 카드들을 트리 모양으로 묶어서 관리하는 ..

문제 개요문제 링크 : https://www.acmicpc.net/problem/11866 요세푸스 문제 (Josephus Problem) 는 다음과 같은 규칙을 가진 사람 제거 시뮬레이션 문제입니다. N명의 사람이 원을 이루고 앉아있고, K번째 사람을 순서대로 제거해 나간다고 할 때,제거되는 사람의 순서를 구하는 문제입니다. 예를 들어 N = 7, K = 3 일 경우 제거 순서는 다음과 같습니다. 7명의 사람이 있고 3번째 사람을 계속 제거한다면1, 2, (3), 4, 5, 6, 7 → 3 제거1, 2, (3), 4, 5, (6), 7 → 6 제거 (7부터 시작)1, (2), (3), 4, 5, (6), 7 → 2 제거 1, (2), (3), 4, 5, (6), (7) → 7 제거 1, (2), (3)..

문제 링크: https://www.acmicpc.net/problem/10866분류: 자료구조, 덱, 구현난이도: 실버 4 문재 개요정수를 저장하는 덱(Deque) 을 구현하고 다음 명령들을 처리하는 문제입니다. 입력 예시:15push_back 1push_front 2frontback 출력 예시:21202 문재 해석덱이란?─ Deque (Double-Ended Queue): 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다.push_front, push_back : 앞/뒤로 원소 삽입pop_front, pop_back : 앞/뒤에서 원소 제거size, empty : 현재 덱 크기 및 비었는지 확인front, back : 양쪽 끝의 값을 확인 (단, 삭제하지 않음) 문제 접근 방식단순한 list 사용은 pop(0..

문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 ..

Recursion - 자기 자신을 호출하는 함수 void func(...) { func(...); } 위 함수를 실행코드로 짜보자 public class Recursive1 { public static void main(String[] args) { func(); } public static void func(int k) { System.out.println("Hello"); func(); } } 위와 같은 코드를 실행하게 되면 return문이 없기 때문에 무한 반복으로 Hello를 출력하면서 에러가 발생하게 된다. 그럼 Recursion은 항상 무한루프에 빠질까? 그건 아니다. 또 하나의 코드를 보자 public class Code02 { public static void main(String[] ar..

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다..