본문 바로가기

ALGORITHM

 (212)
백준 11052 카드 구매하기 (Java) 1. 문제 링크 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp 느낌으로 풀었다. N개의 카드를 제일 비싸게 샀을 때의 가격을 구하는 문제이다. 카드를 살 때마다의 가격을 price 배열에 저장했다. 반복문을 돌리면서 N개를 살 때의 가격을 더해가면서 더 큰 값을 sum 배열에 남겼다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; public class Main { private static int N..
백준 2096 내려가기 (Java) 1. 문제 링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 최솟값과 최댓값을 저장하는 배열을 따로 만들었고 처음 입력받은 줄을 배열에 저장한 상태에서 시작한다. 계속해서 입력받으면서 비교 범위에 있는 값들 중 큰 값과 입력받은 값을 더해 저장한다. 전부 입력 받은 후에 저장된 값들 중 최솟값과 최댓값을 찾는다. 주의할 점은 비교할 때 이후에 입력받은 값들 중 크거나 작은 값이 아니라, 이미 저장된 값들 중 크거나 작은 값을 찾아 더하는 방식으로 진행해야 한다. 비교하는 값을 어..
백준 11057 오르막 수 (Java) 1. 문제 링크 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp로 배열에 저장하면서 풀었다. 한 자리 숫자는 자기 자신만 오르막 수이기 때문에 dp가 1이다. 그 이후의 숫자는 2자리(1-11, 12...19 / 2- 22, 23..29) 예와 같이 (9 - 첫번째 자리 수) 이다. 입력받은 자리수까지 진행하는 i 반복문 / 0부터 9까지 도는 j 반복문 / j보다 크거나 같은 수로 도는 k 반복문을 돌면서 dp[i][j]에 dp..
백준 10431 줄세우기 (Java) 1. 문제 링크 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 20명을 차례대로 줄 세우는 문제이다. list(height)를 만들어서 학생 한 명씩 넣는 과정에서 list에서 지금 입력값보다 큰 값이 나오는 순간의 인덱스를 구한다. 그렇게 하면 뒤로 한 걸음씩 물러서야 하는 학생의 수를 전체 list의 크기 - 현재 인덱스 -1이 된다. 그 과정을 반복하면 답이 나온다. 4. 코드 import java.io.BufferedReader; import java.io.IOExc..
백준 11866 요세푸스 문제 0 (Java) 1. 문제 링크 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 원형으로 앉아있는 사람 중 K번째 사람을 계속 제거해서 전부 제거하면 된다. 큐를 활용해서 구현하면 간단하게 할 수 있다. K번째가 되기 전의 정수는 큐에서 빼서 바로 다시 큐에 넣고, K번째 사람은 빼서 출력하면 된다. 4. 코드 import java.io.IOException; import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class Main { public static void m..
백준 21921 블로그 (Java) 1. 문제 링크 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 주어진 기간의 총 방문자 수를 구하는 문제이다. 이런 문제는 누적합을 이용하면 빠르게 구할 수 있다. 입력받을 때마다 누적합을 배열에 저장한다. 기간이 3일 경우 반복문을 이용해 arr[N+3] - arr[N]을 하면 그 기간동안의 누적 방문자 수가 나온다 4. 코드 import java.io.BufferedReader; import java.io.IOException; public class Mai..
백준 1003 피보나치 함수 (Java) 1. 문제 링크 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 N번째 피보나치 수를 구하는 과정에서 1번째 피보나치 수와 0번째 피보나치 수가 몇 번 호출되었는지를 구하는 문제이다. 초반인 0번 피보나치와 1번 피보나치를 잘 설정한다면 풀 수 있다. 그 이후에는 원래 피보나치를 구하는 것과 같이 arr[i] = arr[i-1] + arr[i-2]를 하면 된다. 이 식이 그대로 적용되는 이유는 N번째 수를 구하기 위해서는 N번과 N-1번째 수가 필요하고 그 과정을 쭉쭉.. 하면 결국 0번과 1번을 호출하게 되는데 그 과정에서 저장된 값을 계속 사용해야 하기 때문이다..
백준 1074 Z (Java) 1. 문제 링크 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 분할정복의 대표적인 문제이다. 4개의 범위로 나눠서 각 범위 안에 들어왔을 때 재귀한다. 점점 작은 범위가 되고 값을 찾게 된다면 size가 1이 되면서 재귀가 끝난다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static int visit, R, C; publi..

티스토리툴바