코딩테스트
[백준] 용돈 관리
https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이진탐색을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 현우가 용돈을 사용하는데 계획적으로 사용합니다. 그래서, N일 동안의 지출 계획이 있고, 정확하게 M번만 K원씩 인출하여 사용하려 합니다. 이 때, K의 최솟값을 구해야 합니다. 문제를 한번 읽어보는 것을 추천합니다. 통장에서 인출해야 하는 금액 K는 N일간의 지출 계획중 가장 큰 값 보다는 크거나 같아야 하고, N일간의 지출을 모두 더..
[백준] 표절
https://www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 이진탐색을 이용하는 문제입니다. 문제부터 간단하게 요약하면, 파일의 유사도 검사를 해야하는데, 검사할 파일이 너무 많기에 각각의 두 파일을 모두 검사를 하게 되면, 너무 오래걸립니다. 그래서 두 파일이 있을 때, 두 파일의 크기가 [작은파일의 크기 >= 0.9*큰파일의 크기] 인 쌍들에 대해서만 검시를 하려 한다고 합니다. 이 때..
[백준] Social Distancing
https://www.acmicpc.net/problem/18877 18877번: Social Distancing The first line of input contains $N$ and $M$. The next $M$ lines each describe an interval in terms of two integers $a$ and $b$, where $0 \leq a \leq b \leq 10^{18}$. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of a www.acmicpc.net 이분탐색을 이용하는 문제입니다. 문제부터 간단하게 요약하면, 잔디의 구간들이 M개 있는데, 이 구간에 N마리의..
[백준] 폭탄제조
https://www.acmicpc.net/problem/2977 2977번: 폭탄제조 효진이는 돈이 매우 많은 대학생이다. 어느 날, 효진이가 열심히 공부한 과목의 교수가 F학점을 주겠다고 '농담'을 했다. 하지만 효진이는 화가 나서 폭탄을 마구 만들어내 효진이가 소유한 개인 www.acmicpc.net binary search를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1개의 폭탄을 만들기 위해선, N개의 부품 종류가 필요합니다. N개의 줄에 각 줄마다 각각 폭탄 1개에 필요한 부품의 수, 이미 있는 부품의 수, 소형 패키지의 부품수, 소형 패키지의 가격, 대형 패키지에 있는 부품수, 대형 패키지의 가격이 주어질 때, M달러를 이용하여 폭탄을 최대한 만든다면, 몇개 만들수 있는지 구해야..
[정올] 저글링 방사능 오염
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. 출발 지점을 지나는 버스들을 ..