본문 바로가기

분류 전체보기

 (215)
백준 11650 좌표 정렬하기 (Java) 1. 문제 링크 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 좌표를 정렬하기 위해 클래스를 만들어서 x, y를 관리했다. 정렬을 위해 클래스에 Comparable 인터페이스를 구현한다. 그 중 compareTo()를 재정의해 x좌표 비교 후 y좌표를 비교하도록 했다. 이후에 Arrays.sort()를 이용해 배열을 재정의한 순으로 정렬한다. 4. 코드 import java.io.BufferedReader; impo..
백준 21608 상어 초등학교 (Java) 1. 문제 링크 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 학생에 대한 정보를 입력받으면서 자리를 찾는다. (이 자리가 정해져야 다음 자리를 정할 수 있기 때문) 모든 자리를 탐색하면서 인접칸에 좋아하는 학생의 수를 체크하고, 빈칸의 수를 체크한다. 1번 조건 확인 - 좋아하는 학생이 가장 많은 자리를 찾는다(list에 자리 추가) 2번 조건 확인 - 1번 조건이 1인 경우 자리 배치, 1보다 큰 경우 다음 조건을 확인한다. 4-1. 빈 칸이 가장 많은 ..
백준 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..

티스토리툴바