백준/JAVA

[백준/JAVA] 11659번 구간 합 구하기 4

누적 합 테크닉으로 구간 합을 빠르게 구하는 문제 https://www.acmicpc.net/problem/11659 1. 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 2. 문제 접근 1) 첫째 줄에 수의 개수 N과 합을 구하는 횟수 M을 입력받는다. 2) 둘째 줄에서 N개의 수를 입력받을 때 배열에 누적합을 저장한다. 3) 셋째 줄부터 M번 만큼 시작 인덱스와 종료 인덱스를 입력받고 누적합 배열에서 종료 인덱스 값에서 시작 인데스-1 값을 빼줌으로 구간의 합을 구한다. 3. 코드 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; impor..

[백준/JAVA] 14852번 타일 채우기 3

https://www.acmicpc.net/problem/14852 1. 문제 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 2. 문제 접근 1) 첫째 줄에 길이 N을 입력받는다. 2) 타일 채우기의 규칙을 파악한다. 2-1) N이 1일 때 경우의 수는 2, N이 2일 때 경우의 수는 7이다. 2-2) N이 3이상일 때 N-1 크기에서 채우는 경우의 수는 2가지이다. 2-3) N-2 크기에서는 채우는 경우의 수는 3가지이다. 2-4) N-(3이상) 크기에서는 채우는 경우의 수는 2가지이다. 3) 재귀적으로 표현시 시간초과가 발생하기 때문에 모든 타일 채우는 경우의 수 배열의 2배를 더한 값을 저장하고 N번 째 경우의 수는 2배를 더한 값 + N-2의 경우의 수로..

[백준/JAVA] 2133번 타일 채우기

https://www.acmicpc.net/problem/2133 1. 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 2. 힌트 3. 문제 접근 1) 첫째 줄에 N의 크기를 입력받는다. 2) 경우의 수를 고려한 후 다이나믹 프로그래밍에 대한 점화식을 세운다. 2-1) 홀수인 경우 칸의 총 수가 홀수이기 때문에 2X1 혹은 1X2 크기의 타일로 채우지 못하기 때문에 0을 반환한다. 2-2) 짝수인 경우 크기가 2 작은 타일에서 채우는 경우의 수가 3가지이기 때문에 N-2를 매개변수로 하는 재귀함수에 3을 곱하는 경우를 가진다. 2-3) 짝수인 경우 중에 크기가 2보다 큰 짝수(4,6,8)만큼 작은 타일에서 채우는 경우의 수가 2가지이기 때문에 N-(2보다 큰 짝수)를..

[백준/JAVA] 2156번 포도주 시식

규칙에 따라 포도주를 마실 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제 https://www.acmicpc.net/problem/2156 1. 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있..

[백준/JAVA] 10844번 쉬운 계단 수

동적 계획법을 이용해 계단 수를 구하는 문제 https://www.acmicpc.net/problem/10844 1. 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 2. 문제 접근 1) 첫째 줄에 계단 수의 길이 N을 입력받는다. 2) 자리 수가 1일 때는 1부터 9까지 한개씩이기 때문에 0~9를 인덱스로 가지는 int형 배열에 1부터 9까지 인덱스의 value를 1로 정한다. 3) 자리 수 만큼 반복하면서 끝 수의 위 아래 수의 인덱스에 기존의 값들을 더해주고 마지막에 기존에 있던 수들을 빼주는 형식으로 계단 수를 구할 수 있다. 3...

[백준/JAVA] 1764번 듣보잡

듣도 보도 못한 문제 https://www.acmicpc.net/problem/1764 1. 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 2. 문제 접근 1) 듣도 못한 사람의 수 N과 보도 못한 사람의 수 M을 입력받는다. 2) 듣도 못한 사람과 보도 못한 사람을 입력받는다. 3) 듣도 못한 사람을 입력받을 때 이를 HashSet에 저장한다. 4) 보도 못한 사람을 입력받을 때 HashSet에 존재하면 이를 ArrayList에 저장한다. 5) ArrayList를 정렬한다. 6) 지정된 출력형식으로 출력한다. 3. 코드 import java.io.IOException; import java.io.InputStr..

[백준/JAVA] 9184번 신나는 함수 실행

간단한 동적 계획법 문제 https://www.acmicpc.net/problem/9184 1. 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 ..

[백준/JAVA] 9663번 N-Queen

조금 더 복잡한 백트래킹 문제 1 https://www.acmicpc.net/problem/9663 1. 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 2. 문제 접근 1) 첫째 줄에 체스판의 크기 N을 입력받는다. 2) 퀸이 공격할 수 없으려면 한 행에 한개씩 두어야한다. 3) 백트래킹 알고리즘을 사용하여 depth를 행으로 생각, 0부터 N-1까지 반복하며 열을 선택한다. 4) 이때, 열, 2개의 방향의 대각선에 겹치면 안되기 때문에 체크를 하는 boolean형 배열 3개를 선언한다. 5) 열, 2개의 방향의 대각선 모두 겹치지 않을 때 백트래킹 함수를 실행하고 각 체..