https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 백준 11053번 가장 긴 증가하는 부분 수열 문제 링크입니다. 핵심 동적 계획법을 사용하여 푸는데, 증가하는 수열을 만들 때, 가장 큰 길이를 구하는 것이다. 그전 값을 비교하며 더 커지면 dp를 증가시키는 형태이다. 정답 코드 import java.util.Scanner; public class Main { publ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 백준 2156번 포도주 시식 문제 링크입니다. 핵심 이 문제는 저번에 풀었던 계단 오르기와 매우 유사한 문제이다. https://kimtaesoo99.tistory.com/31 [백준]2579번 계단 오르기 https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.a..
https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 백준 1094번 막대기 문제 링크입니다. 핵심 문제를 해석해보면 매우 쉬운 문제라는 것을 알 수 있다. 64보다 작거나 같은 자연수를 2진수로 바꾸었을 때, 1의 개수를 구하는 것이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 백준 1463번 1로 만들기 문제 링크입니다. 핵심 단순하게 3으로 나누고, 2로 나누고, 1을 빼는 순서로 풀게 된다면, 함정에 걸린 것이다. 바로 10이 그 예시이다. 제일 적게 조합해서 만드는 방법을 0부터 차례대로 생각해야 한다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 백준 2579번 계단 오르기 문제 링크입니다. 핵심 계단을 1칸, 2칸 이동 가능하다. 마지막 계단은 반드시 밟아야 한다. 3개 연속으로 계단은 올라갈 수 없다. 가장 중요한 것이 3개의 계단을 연속으로 올라갈 수 없다는 것이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner ..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 1912번 연속합 문제 링크입니다. 핵심 연속된 수의 합이 가장 큰 값을 찾는 것이다. 이전까지 탐색했던 값과 새로운 값을 비교해나가면 쉽게 풀 수 있다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = i..
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 백준 9184번 신나는 함수 실행 문제 링크입니다. 핵심 동적 계획법을 사용하는 것인데, 재귀와 메모이제이션을 사용한다. 정답 코드 import java.util.Scanner; public class Main{ public static int[][][] arr = new int[21][21][21]; public static void main(String[] args) { Scanner sc = n..
https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 백준 2164번 카드 2 문제 링크입니다. 핵심 큐를 사용하면 쉽게 풀 수 있는 문제이다. 가장 먼저 넣은 수를 제거하고, 그 뒤의 수를 맨뒤로 보낸다. 카드가 1개 남았을 때까지 반복한다. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public stat..
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 9663번 N-Queen 문제 링크입니다. 핵심 N*N크기의 체스판에 N개의 퀸을 놓는다. 퀸은 일직선, 대각선으로 쭉 움직일 수 있다. 즉 각각의 퀸이 일직선과 대각선에 위치하면 안 된다. 1차원 배열을 사용하여, 각 배열의 index를 열, 값을 행으로 본다. 정답 코드 import java.util.Scanner; public class Main { public static int[] arr; publ..
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 백준 14888번 연산자 끼워넣기 문제 링크입니다. 핵심 N개의 수를 받고, N-1개의 연산자를 받는다. 모든 경우의 수를 찾아야 한다. 즉 백트래킹을 통해 모든 경우의 수를 확인하는 재귀 호출 문제이다. 정답 코드 import java.util.Scanner; public class Main { public static int max=Int..
