본문 바로가기

백준

 (55)
백준: 21761번 (초직사각형) [JAVA] 문제 링크 https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 각 A, B, C, D에 대한 좌표와, 각 카드 속 특정 좌표의 증가분을 저장할 long 타입 배열 생성 후 초기화 각 좌표 별 증가분을 내림차순으로 정렬하는 우선순위 큐들을 생성 후, 주어지는 카드들 속 증가분을 저장 K 번에 걸쳐 아래 작업을 반복 1) 각 좌표에 대한 우선 순위 큐에서 증가분을 꺼내 저장 (만약 없다면 0) 2)..
백준: 14908번 (구두 수선공) [JAVA] 문제 링크 https://www.acmicpc.net/problem/14908 14908번: 구두 수선공 최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 주어진 작업에 대한 정보를 가진 하나의 클래스 생성 (작업 번호, 작업일, 보상 금액) 1) 추가로 이들 간의 비교 가능한 Comparable 구현 작업에 대한 개수 N 입력 받음 이후 N번에 걸쳐 받은 정보를 바탕으로 작업 클래스 생성해 우선순위 큐에 모두 저장 그 다음 우선순위 큐에서 작업들을 모두 하나씩 꺼내 작업 번호 출력 문제에서는..
백준: 16207번 (직사각형) [JAVA] 문제 링크 https://www.acmicpc.net/problem/16207 16207번: 직사각형 길이가 5, 6, 6, 6인 막대 중에서 길이가 6인 막대 하나의 길이를 5로 줄여 넓이가 30인 직사각형을 만들 수 있다. 그 다음, 길이가 3, 4, 4, 4인 막대 중에서 길이가 4인 막대 하나의 길이를 3으로 줄여 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 막대 개수 N과 막대 길이들을 입력받아 배열(bars) 생성, dp용 배열(long 타입) 생성 막대 길이가 저장된 배열 bars를 내림차순 정렬 막대 길이의 맨 앞부터 막대가 4개 남을 때까지, 막대를 하나씩 제외 시켜가며 재귀 함수 기반 탐색 call 결과 반환 문제에서 요구하는 답은 결국 주어진 막대들에서 최대한..
백준: 18808번 (스티커 붙이기) [JAVA] 문제 링크 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 주어지는 패널의 사이즈와 스티커들의 정보를 저장 문제에서 요구하는 방식대로 순서대로 스티커를 회전, 이동하며 붙일 수 있는 패널에 부착 스티커를 붙이며 해당 스티커가 차지하는 칸을 반환하며 이를 모두 답에 누적 후 반환 문제 해결을 위해 특정 알고리즘을 필요로 하기 보다는, 문제 요구하는 바를 구대로 구현할 수 있는 지를 보는 구현 문제에 가깝다...
백준: 1043번 (거짓말) [JAVA] 문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 주어지는 진실을 아는 사람과, 파티 참가인원 정보를 바탕으로 진실을 아는 사람이 참가하는 파티, 파티에 대한 참가자들로 구성된 인접리스트 초기화 이후 진실을 아는 사람들을 시작으로 dfs 탐색을 진행 전체 파티 중에서 방문한 적이 없는 파티들의 개수를 반환 문제에서 원하는 답인 과장된 이야기를 할 수 있는 파티의 개수를 구하려면, 진실된 이야기를 아는 사람..
백준: 1865번 (웜홀) [JAVA] 문제 링크 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 주어진 도로와 웜홀의 정보를 바탕으로 전체 지점간의 이동 cost를 저장하는 2차원 배열을 초기화 이후 해당 배열을 바탕으로 플로이드-와샬 알고리즘을 통해 전체 최단거리 cost를 계산 그 다음 2차원 배열 속 (i, i) 지점을 돌며 해당 지점이 음수 값이 있는 지를 통해 시간이 줄어들며 출발 위치로 돌아올 수 있는 지를 확인 후 ..
백준: 17144번 (미세먼지) [JAVA] 문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 문제에서 요구하는 대로 공기청정기를 통한 먼지의 이동 함수, 각 먼지들이 퍼지는 함수를 구현 주어진 T초마다 이들을 반복 호출 후, 남은 먼지들의 총 합을 계산해 반환 문제 해결을 위한 알고리즘 구현 난이도는 거의 없지만, 문제 자체에서 요구하는 로직 구현이 상당히 복잡하여 이들을 구현하는 것이 핵심인 문제이다. 우선 문제에서도 보이다시피 초마..
백준: 2638번 (치즈) [JAVA] 문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 전체적인 풀이 과정은 다음과 같다. 우선 주어진 데이터를 저장할 2차원 배열 초기화 외부와 접촉한 공기를 체크하는 BFS 함수를 통해 2차원 배열에 표시 전체 2차원 배열 속 녹을 수 있는 치즈 좌표를 큐에 저장한 후, 전체 큐 속 치즈 좌표들을 공기로 바꾸며 추가적인 외부와 접촉한 공기 표시 작업을 진행 3번의 과정을 전체 while문으로 돌며 그 때마다 answer..

티스토리툴바