본문 바로가기

ALGORITHM

 (212)
백준 16435 스네이크버드 (Java) 1. 문제 링크 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 과일의 높이를 정렬한다. 뱀의 길이와 비교하면서 과일의 높이보다 뱀이 길거나 같다면 과일을 먹을 수 있다. 과일 배열에서 첫번째를 지우고 뱀의 길이를 +1한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..
백준 3040 백설공주와 일곱 난쟁이 (Java) 1. 문제 링크 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 일곱 난쟁이 모자에 적힌 숫자를 전부 더한다. 거기서 두 값을 빼면서 100이 되는 경우를 찾았다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws Excep..
백준 9084 동전 (Java) 1. 문제 링크 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp로 하는데 money[만들 수 있는 가격]에 경우의 수를 저장한다. 동전마다 만들 수 있는 경우의 수를 money 배열에 더한다. money 배열은 해당 동전으로 만들 수 있는 인덱스부터 시작해야 하기 때문에 j=i부터 시작하게 했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Input..
백준 18870 좌표 압축 (Java) 1. 문제 링크 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 일단 clone()을 이용해 배열을 복사한다. 배열을 정렬하고 그 순서대로 HashMap에 추가한다. (Map이 중복 불가이기 때문) 그러면 그 보다 작은 수의 개수는 i가 아니라 index로 별도로 구해야 한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..
백준 2563 색종이 (Java) 1. 문제 링크 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 100x100 도화지에 10x10 색종이를 붙인다. x 좌표와 y 좌표를 입력받을 때마다 반복문을 돌려서 각각 10칸씩 방문했다고 체크한다. 색종이 개수만큼 반복문을 돈 이후에는 전체 도화지에서 방문했던 칸의 수를 센다. 그 수가 바로 검은 영역의 넓이이다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class M..
백준 1992 쿼드 트리 (Java) 1. 문제 링크 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 N이 언제나 2의 제곱수라는 것에서 분할 정복을 해야한다고 생각했다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 압축이 된다고 하니 4분면으로 나누고 재귀를 했다. => round 메서드 (시작 x 좌표, 시작 y 좌표, 탐색할 길이) 만약 4분면이 모두 동일한 값이라면 재귀를 하지 않고 값을 내보낸다. => same 메서드 (시작 x 좌표, 시작 y 좌표, 검사할 길이) 4. 코..
백준 11286 절댓값 힙 (Java) 1. 문제 링크 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 절댓값 힙이라는 문제 이름에서 알 수 있듯이 PriorityQueue를 이용했다. 절댓값이기 때문에 익명클래스를 이용해 Comparator로 비교하는 과정을 만들었다. 입력받은 값을 큐에 추가를 하는 과정에서 비교를 하게 된다. 기존 compare을 사용하는 방식을 유지하지만 절댓값이 같은 경우 작은 값이 우선순위가 되도록 했다. 4. 코드 import java.io.BufferedRe..
백준 23971 ZOAC 4 (Java) 1. 문제 링크 23971번: ZOAC 4 i행 j열 자리를 (i, j)라고 할 때, (1,1)에 참가자가 앉은 경우 다른 참가자는 (1,2), (2,1), (2,2) 자리를 제외한 나머지 자리에 앉을 수 있다. (2,2)의 경우는 (1,1)과 행 번호 및 열 번호의 차가 1보다 크 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 일단 1명이 앉고, N칸 띄우고 1명이 앉는 게 반복되면 최대 인원이 앉을 수 있다. 주어진 H에서 1명이 앉을 자리를 뺀 값에서, N칸 띄우고 1명이 앉았을 때의 값에 처음에 앉은 1명을 더하면 된다. W도 똑같이 해서 나온 값을 곱하면 강의실이 수용할 수 있는 최대 인원이 나온다. 4. 코드 import java.io.BufferedReader; imp..

티스토리툴바