백준20 [백준, 1113, 자바] 수영장 만들기 https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 1. 문제 핵심 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직유면제 취의 표면에는 물이 없다. 땅의 높이는 0이고, 땅은 물을 무한대로 흡수할 수 있다. 2. 문제 접근 접근법 1. 한 노드부터 BFS로 주변 노드를 검사. 해당 노드의 높이보다 낮은 노드가 있으면 수영장이 될 수 없다고 판단. 가장자리와 맞닿아있으면 물이 새기 때문에 수영장 불가 판단. visit 배열로 .. 2022. 8. 4. [백준, 18500, 자바] 미네랄2 문제 링크 : https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 1. 문제 핵심 막대기로 인해 분리되는 클러스터는 막대기 당 최대 1개밖에 없습니다. 분리된 클러스터는 낙하하며 다른 미네랄이나 바닥에 부딪히기 전까지 멈추지 않습니다. 왼쪽에 던졌을 때는 클러스터가 [상, 우, 하] 로 발생할 수 있고 오른쪽에서 던졌을 때는 클러스터가 [상, 좌, 하] 로 발생할 수 있습니다. 2. 문제 접근 막대기를 던집니다. 막대기가 미네랄을 만나면 해당 미네랄을 파.. 2022. 7. 25. [백준, 1027, 자바] 고층 건물 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 1. 문제 핵심 빌딩의 수는 최대 50개. 빌딩의 높이는 최대 10억보다 작거나 같은 수 2. 문제 접근 총 빌딩의 수가 50개밖에 되지 않아 완탐으로 한 빌딩과 그 외 나머지 빌딩을 모두 비교하면서 진행해도 괜찮다고 생각했습니다. [현재] 빌딩과 [비교] 빌딩 바닥 사이의 거리 / A빌딩과 B빌딩 꼭지점 사이의 거리 == 기울기 값을 구할 수 있다. 기준 빌딩 왼쪽, 오른쪽 각각 진행하며 각 기.. 2022. 7. 25. [백준, 23791, 자바] K번째 음식 찾기 1 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1 한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면 www.acmicpc.net 1. 문제 핵심 두 종류의 음식이 존재하기 때문에 두 번의 이분 탐색이 필요 한식과 양식 모두 첫번째부터 i, j 번째까지 범위가 존재 2. 문제 접근 이분탐색의 기준으로 특정 한식 배열 중 하나의 값을 사용했다. 그리고 해당 값보다 작은 양식의 개수를 조사해서 한식과 양식이 몇 번째인지 확인하고 두 음식의 번호를 더했을 때 k가 되는지 확인한다... 2022. 7. 7. [백준, 17780, 자바] 새로운 게임 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 1. 문제 핵심 흰색, 파란색, 빨간색 자리 별로 이동이 다르다. 외곽은 파란색과 동일한 타일 취급한다. 최대 1000번까지 루프를 반복하며 그 이상은 -1을 출력한다. 2. 문제 접근 말의 자리와 쌓여있는 높이를 수월히 계산하기 위해서 보드와 해당 보드 칸에 쌓여있는 말의 번호를 저장하는 3차원 배열이 존재하고 각 말들이 어느 행, 열의 칸에 몇 번째 레벨에 쌓여있는지 저장하는 2차원 배열로 관.. 2022. 7. 7. [백준, 3954, 자바] Brainf**k 인터프리터 문제 링크 : https://www.acmicpc.net/problem/3954 3954번: Brainf**k 인터프리터 각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([ www.acmicpc.net 1. 문제 핵심 명령어는 최대 5천만번 이상 수행된 뒤, 항상 종료되거나 무한 루프에 빠진다. 여러 종류의 연산을 수행하고 연상이 종료되는지, 무한 루프에 빠지는지 검사한다. 2. 문제 접근 명령어를 수행하고 5천만번 이전에 끝나면 terminates를 출력 명령어가 5천만번이 수행되었다면 1. 모든 명령어가 수행되었다면 terminates를 출력.. 2022. 6. 22. [백준, 1799, 자바] 비숍 문제 : https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 1. 문제 핵심 1. 비숍은 대각선으로만 움직일 수 있다. 2. 체스판 가로, 세로는 열 개 이하의 칸을 가진다. 3. ↓ 핵심 더보기 흰 색 칸에 속하는 비숍은 검은 색 칸의 비숍에게 간섭을 못하고, 검은 색 칸의 비숍은 흰 색 칸의 비숍에게 간섭하지 못한다. (중요) 2. 문제 접근 1. 백트래킹으로 비숍을 놓을 수 있는 각 칸마다 해당 칸의 좌상 대각선, 우상 대각선에 다른 비숍이 있는지 확.. 2022. 6. 21. 백준 1644 소수의 연속합 [자바] 문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 접근 : 1. 목적수 이하까지의 모든 소수를 구한 다음 슬라이딩 윈도우를 사용해서 크기를 조정해가며 해당하는 값들을 구한다. 2. 1은 소수가 아니다. 팁 : 작은 소수를 구했다면 그 소수를 목적수까지 2,3,4,~ N배를 해주며 예외처리를 해준다. 그러면 자연스레 남은 모든 수들은 소수가 되기 때문에 소수 검출에 시간을 대폭 줄일 수 있다. (i.e. : 에라토스테네스의 체) 더보기 코드 보기 package _0606.ChungLee; import java.io.DataInputStream; i.. 2022. 6. 6. 백준 17472 다리 만들기 2 [자바] 문제 링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 해석 : 1. 연결에 제한이 존재하는 그래프 탐색 문제를 2차원 배열로 표현한 문제 2. 출력 값이 모든 섬을 연결하는 다리 길이의 최솟값이기 때문에 MST로 해결하고자 했음 주의점 : 1. 한 섬에서 출발해서 같은 섬으로 도착할 때는 다른 섬으로 도착한 것이 아님 2. 다른 섬으로 도착했을 때 거리가 2보다 작을 때는 성립하지 않음 3. 모든 섬에 방문할.. 2022. 6. 6. BOJ 16946 G2 벽부수고 이동하기 4 [JAVA] 문제 링크 : https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 문제 ------------------------ N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으.. 2022. 5. 30. 이전 1 2 다음
