전체 글
[정올] 저글링 방사능 오염
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=3040 JUNGOL www.jungol.co.kr BFS를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 저글링에 방사능 오염 공격을 가하게 되는데, 방사능 오염공격을 맞은 저글링은 3초후 죽습니다. 추가적으로 1초마다 오염된 저글링 바로 옆의 저글링에게 오염이 전이됩니다. 이 때, 저글링의 위치와, 공격받는 저글링이 주어질 때, 총 몇초만에 죽을 수 있는 저글링들이 모두 없어지는지를 구해야 합니다. 추가적으로, 죽지않고 남아 있는 저글링의 수도 출력해야 합니다. BFS를 이용해야 합니다. queue를 만들고, 처음 방사능 공격을 받는 저글링을 넣어줍니다. 이 때, r,c,time ..
[백준] 소수 경로
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net BFS를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1033 -> 8179 처럼 소수에서 소수로 변환이 일어나야 하는데, 중간에 변경되는 값들은 1033 1733 3733 3739 3779 8779 8179 처럼 4자리중 1자리 숫자만 달라져야 하고, 각각 또한 소수여야 하고, 1000이상의 4자리 수여야합니다. 이 때, 최소 횟수만에 변환이 일어난다고 하면, 얼마의 변환이 필요한지 출력해야 ..
[백준] 탈출
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 고슴도치가 비버굴로 이동을 해야하는데, 물이 차있는 곳에서 물이 확산되어 홍수처럼 물이 불어납니다. 이 때, 고슴도치는 물이 차있거나, 돌을 지날 수 없을 때, 고슴도치가 비버굴로 이동할 수 있는 가장 빠른 시간을 출력해야 합니다. 만약 이동이 불가능 한 경우 "KAKTUS"를 출력해야 합니다. BFS를 이용해야 하는 것이 확실한데, 물이 차올라..
[백준] 버스 갈아타기
https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net BFS를 이용하는 문제입니다. 문제부터 간단하게 요약하면, 버스들이 그림 처럼 생긴 좌표들 위를 움직이는데, 가로축 혹은 세로축으로 움직입니다. 각각의 버스들이 노선을 가질 때, 주어진 출발지에서 도착지로 도착하는데 최소한으로 이용해야 하는 버스 갯수를 구하는 문제입니다. BFS를 이용해야 합니다. 로직을 생각해 봅시다. 1. 출발 지점을 지나는 버스들을 ..
[백준] 문자열 폭발
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net https://life318.tistory.com/68 [백준] 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크 life318.tistory.com 한번 파이썬으로 해결한 ..
[백준] 히스토그램에서 가장 큰 직사각형
https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net stack을 이용하는 문제입니다. 다양한 풀이들이 많이 있는 문제로 유명하다고 하는데, 다른 방식들을 또 알게되면 추가해 보도록 하겠습니다. 우선 문제부터 간단하게 요약하면, 그림과 같이 히스토그램이 위치할 때, 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이 때, 직사각형의 수는 10만개 까지, 그리고 각각의 높이는 0부터..
[백준] 택배
https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 알고리즘을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 용량이 정해진 택배 트럭이 마을마다 물건을 배송합니다. 이 때, 보내는 마을, 받는 마을, 박스 개수가 주어질 때, 트럭 한대로 배송할 수 있는 최대 박스 수를 구하는 문제입니다. greedy 알고리즘을 활용해야 하는 문제입니다. 간단한 예시로 문제를 살펴봅시다. [INPUT] 4 40 6 3 4 20 1..
[백준] 색종이 - 3
https://www.acmicpc.net/problem/2571 2571번: 색종이 - 3 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net N^6 로직을 활용하여 해결하였습니다. 우선 문제부터 간단하게 요약하면, 흰 도화지 위에 검정 색종이를 붙입니다. 이 때, 검정색 부분을 가장 큰 직사각형 모양으로 잘라내고 싶을 때, 잘라낼 수 있는 가장 큰 넓이를 구해야 합니다. 도화지의 크기가 크지 않으므로, 시작지점(N^2)과 끝지점(N^2)을 찾아서, 해당하는 구간이 모두 검정색이 맞는지 탐색(N^2)을 하면서 만약 맞다면 area의 넓이를 ..