Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/14575 14575번: 뒤풀이 첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109) 둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106) www.acmicpc.net 풀이 먼저, 각 사람들이 최대주량으로 마셨을때 T보다 작거나, 각 사람들이 최소 주량으로 마셨을때 T보다 크다면, 어떠한 경우에도 정확히 T를 맞출 수 없으니 -1을 출력해준다. 위를 통과한다면 이분탐색을 이용하여 문제를 해결한다. 이분탐색을 이용하여 S를 설정해준 뒤, S를 가지고 해당 인원들을 정확히 T만큼 먹일 수 있는지 확인을 한다. 자신의 주량범위 안에서, S를..

2021. 9. 15.

문제풀이/백준oj

https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 풀이 1. 먼저 lower_bound(이분탐색) 함수를 사용하기위해서, 입력받은 발사대를 오름차순 정렬을 해준다. 2. 동물을 입력받음과 동시에, 동물의 x좌표와 가까운 발사대를 lower_bound를 통해 찾는다. 3. 해당 발사대와의 거리가 L 이하라면, answer++를 해준다. 4. 해당 발사대와 거리가 멀다면 , 해당 발사대의 이전 발사대를 조사해 L 이하라면 answer++를 해준다. ..

2021. 9. 14.

문제풀이/백준oj

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 풀이 길이가 최대 20인 문자열이므로, N값이 작기때문에 백트래킹을 이용하여 모든 경우의 수를 구해주면 된다. 이때 알파벳순으로 출력을 해야하므로, 전부다 구한뒤, 중복을 제거하고 정렬을 하는것과 맵에 INSERT해서 출력을 하는것보단, 입력받은 문자열을 구성하는 알파벳들의 개수를 모두 세어준뒤, 알파벳 순서대로 존재하면 추가하고 다음으로 넘어가주는 백트래킹을 이용하면 정렬없이 알파벳 순서대..

2021. 9. 13.

문제풀이/백준oj

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 1. 입력을 받으면서 토마토부분들을 queue에 push해주고, 익지않은 토마토의 개수를 세어준다. 2. queue에 들어있는 토마토들을 가지고 bfs를 실행해준다. 이때 오늘익은 토마토가 같은날 주변의 다른 익지않은 토마토를 익지 못하게 하기위해, 어제익었던 토마토들만 bfs를 돌리며 날짜를 +1해준다. 또한 토마토들이 익을때마다 익지않은 토마토의 개수를 -1 해준다..

2021. 9. 12.

문제풀이/백준oj

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 최단거리를 구하기 위한 알고리즘 중 다익스트라 알고리즘을 이용했다. 다익스트라 알고리즘을 이용해서, 먼저 S지점, H지점, G지점에서 각각 모든지점까지의 최단거리를 구해준다. 그런뒤, S에서 각 목적지까지의 거리가, S->H->G->목적지 또는 S->G->H->목적지 까지의 거리와 같다면, 요란한 옷차림을 한 서커스 예술가들이 H와 G도시 사이에 있는 경로를 지나왔다는 의미가 되므로, ..

2021. 9. 11.

문제풀이/백준oj

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 스택을 이용해도되고, 스택의 개념을 이용해 일반 변수를 선언하여 풀이를 해도된다. 1. 여는괄호를 만나면 파이프의 개수를 추가해준다. 2. 닫는괄호를 만나면, 레이저인지 아닌지를 판별해서 각 상황에 맞게 계산해준다. 2-1. 닫는괄호를 만났을때, 바로앞 괄호가 여는괄호라면, 레이저 이므로, 현재까지 만난 파이프에서 1을 빼준뒤, 정답에 현재 파이프값 만큼 더해준다. 현재까지 만난 파이프의 개수에서 -1..

2021. 9. 10.

문제풀이/백준oj

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 먼저 그래프를 입력받은뒤, 각 정점마다 bfs를 이용하여 트리를 검사한다. 한 정점에서 연결된 모든 정점들이 사이클이 없다면, tree를 1 증가시키고, 사이클이 존재한다면 tree를 존재하지 않는다. 이 bfs를 이용할때, 이전에 검색했던 정점들의 흔적을 남겨놓고, 다음번에 다시한번 검사하는 일이 없도록 코드를 짜면된다. 시간복잡도 테스트케이스를 T, 각 테스트케이스 마다..

2021. 9. 9.

문제풀이/백준oj

https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 풀이 누적합과 Map을 이용해서 문제를 해결했다. 입력과 동시에 1번째수~i번째수의 합을 psum배열에 저장을 해놓음과 동시에, 1~i번째수의 합이 K라면, answer++를 해준다. 그런뒤, psum[i]= 1~i번째까지의 합이라고 했을때, psum[i]-psum[j-1]=k에서 k의 값은 j~i까지의 합이 된다는 개념을 이용해..

2021. 9. 7.