본문 바로가기

728x90

백준

[백준] 17143 낚시왕 / 자바(Java) 문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 해설 상어 객체를 만들어 낚시왕이 상어를 잡는 부분에는 상어배열을, 상어가 이동하는 부분에는 상어 큐를 사용해서 해결하였습니다. 상어의 이동 부분에 상어 큐를 사용한 이유는 상어의 이동들은 모두 동시에 이동하기 때문에 큐로 상어 객체이 이동된 이후의 값을 추가하며 넣고 배열에 다시 넣으며 상어끼리 먹는 구간을 구현했습니다. 코드 import java.io.BufferedR.. 더보기
[백준] 17144 미세먼지 안녕! / 자바(Java) 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 해설 2차원배열에서의 탐색을 구현하는 문제입니다. 크게 2단계로 이루어져 있으며 미세먼지가 확산되는 단계와 공기가 순환하는 단계가 있습니다. 1단계 : 미세먼지 확산 확산의 규칙 1. 인접한 네 방향으로 확산하되 벽과 공기청정기로는 확산되지 않는다. 2. 확산된 곳에는 (본래의 값/5) 의 값만큼 먼지가 추가된다(소수점자리는 이산수학으로 / 사용시 제거된다) 3. 본래의 위치에는 (본래의 .. 더보기
[백준] 18111 마인크래프트 / 자바(Java) 문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 해설 높이 있는 블럭은 낮추고, 낮게 있는 블럭은 높여 평평하게 고르는데 필요한 최소한의 시간을 구하는 문제입니다. 일일히 하나씩 빼고 넣기에는 너무 구현이 복잡해 질 듯하여 높이의 제한이 256인 것을 보고 모든 높이를 대입해보자는 브루트포스 방식을 사용하기로 했습니다. 가로, 세로는 각각 500이므로 모든 높이에서의 시간을 확인해 보는데 256*500*500으로 계산해 볼만한 시간복잡도.. 더보기
[백준] 22352 항체 인식 / 자바(Java) 문제 https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 해설 문제에 나오는 CPCU-1202 백신은 2차원 배열 중 단 한곳에 떨어지고, 그 떨어진 곳과 인접하며 같은 숫자인 위치로 퍼지며 모두 퍼지게 된 이후에 함께 어떤 특정 값으로 바뀌는 특징이 있습니다. 문제의 입력값은 2차원 배열의 이전 모습과 이후 모습을 주며 해당 백신이 들어갔을 가능성이 있는가를 파악하는 것이 문제입니다. 문제의 풀이방식은 .. 더보기
[백준] 9205 맥주 마시면서 걸어가기 / 자바(Java) 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 해설 기초적인 BFS문제입니다. 편의점의 좌표만이 나와있기 때문에 어느 편의점을 방문했는가 여부를 알기위해 입력값을 받을 때 편의점별로 추가로 인덱스를 저장하여 줍니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedLis.. 더보기
[백준] 9576 책 나눠주기 / 자바(Java) 문제 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 해설 그리디 알고리즘을 사용해 가장 많은 책을 주는 방법을 찾습니다. 책의 범위에서 시작의 오름차순으로 정렬해 그 중 가장 앞에 있는 것부터 하나씩 준다고 생각합니다. 책은 1~N까지로 정해져있기 때문에 selected배열을 통해 준 책과 안준 책을 분류합니다. 이후 책 범위를 정렬해 각자 최저번호에 가까운 책을 줍니다. 코드 import java.io.BufferedReader; import .. 더보기
[백준] 2239 스도쿠 / 자바(Java) 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 해설 스도쿠를 해본 분이라면 상상만 했던 스도쿠를 자동으로 푸는 코드를 짜는 문제입니다. 구현문제로 큰 어려움 없이 필요한 동작들을 순서대로 실행하면 가능합니다. 1. 빈칸들을 확인하기 2. 빈칸에 들어갈 수 있는 수를 하나씩 넣어보기 3. 다음 빈칸을 확인하기 4. 2와3을 반복하며 모든 빈칸에 옳은 값을 넣은 경우 반복종료 사람과는 달리 컴퓨터는 예측이 아닌 모든 수를 넣고 가능한 .. 더보기
[백준] 2136 개미 / 자바(Java) 문제 https://www.acmicpc.net/problem/2136 2136번: 개미 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각 www.acmicpc.net 해설 직선상에 있는 여러 개미들 중에 마지막으로 떨어지는 개미의 순번과 떨어지는 시간을 구하는 문제입니다. 처음에는 일일히 구현으로 해결해 보려했으나 시간초과로 실패해 찾아본 결과 나온 풀이는 '떨어지는 시간' 과 '마지막으로 떨어지는 개미'를 나누어 구하는 것 입니다. 문제의 작동방식을 보고 분석을 통해 이를 위한 근거를 알아내었습니다. 1. 떨어지는 시간 - 개.. 더보기

728x90