박카스러버

https://www.acmicpc.net/problem/25195 25195번: Yes or yes 첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 www.acmicpc.net 저는 dfs를 이용해 문제를 해결하였습니다. dfs를 이용해 팬을 안 만나는 경로가 있는지를 판단하였습니다. 현재 팬을 만났다면 false를 리턴하고, 다음으로 갈 경로가 없다면 true 리턴합니다. (다음 경로가 없을 때 까지 진행하기 때문입니다.) 다음 경로를 돌면서 팬을 만날 수 없는 경로가 있다면 true로 바꾸고 결과를 ..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 저는 DP를 이용해 문제를 해결하였습니다. 일단 전화식은 f(n) = f(n-1) + f(n-2)로 구하였습니다. n번째 칸에 세로로 2인 직사각형을 넣으면 f(n-1)값이 되고, 가로로 2인 직사각형 2개를 넣으면 f(n-2)값이 되기 때문입니다. 이 값을 DP에 저장하며 문제를 해결하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputS..

https://www.acmicpc.net/problem/10917 10917번: Your life 당신이 꿈을 이루는 과정 중에 일어날 수 있는 수많은 상황들의 관계를 그래프로 나타내어 보겠다. 많은 상황을 압축해서 N개의 상황이 일어날 수 있다고 하고 1번에서 N까지의 번호를 붙였다. www.acmicpc.net 저는 BFS를 통해 문제를 해결하였습니다. 시작점(1)부터 시작하여 bfs로 진행하면서 n까지 도달할 수 있는지 도달한다면 해당 time은 몇인지를 판단하여 문제를 해결하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import j..

https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 저는 재귀를 이용해 문제를 해결하였습니다. 해당 문자를 사용했는지 안했는지를 체크하고 안 했다면 cnt(결과 길이)값을 늘립니다. '(' 라면 앞의 숫자를 빼고 cnt를 줄입니다. (앞의 숫자는 길이로 들어가지 않고 곱셈에 활용되기 때문입니다.) 앞의 숫자 * 재귀 함수를 통해 괄호 안에 있는 결과를 가져오고 곱합니다. ')' 라면 지금 cnt를 리턴하여 문제를 해결하였습니다. package..

https://www.acmicpc.net/problem/14677 14677번: 병약한 윤호 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 약을 먹어야 하는 날짜인 N이 주어진다. (1 ≤ N ≤ 500) 두 번째 줄에는 3N개의 약의 상태가 주어지는데, 아침 약은 B, 점심 약은 L, 저녁 www.acmicpc.net 저는 BFS를 이용해 문제를 해결하였습니다. 보통의 BFS는 현재 어디에 있는지를 저장하였지만, 저는 현재 맨 앞, 맨 뒤를 가리키는 값을 저장하였습니다. 해당 값이 현재 먹어야 할 약의 종류와 같은지를 확인하고 같다면 BFS를 진행하여 문제를 해결하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.I..

https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. 저는 현재 태크의 부분인지 아닌지를 확인하고 태크라면 스택에 들어있는 것을 다시 뒤집어서 결과값에 넣었고, 태크가 아니라면 스택에 있는 것을 그대로 결과값에 넣어서 문제를 해결하였습니다. package BOJ.etc; import java.io.BufferedReader; import java.io.InputStreamRea..

https://www.acmicpc.net/problem/15270 15270번: 친구 팰린드롬 초등학생인 재홍이는 이번 봄 학예회 때, 재홍이가 지휘를 맡고 반 친구들이 춤을 추기로 계획했다. 이 춤은 시작할 때 춤추는 친구들이 일렬로 쭉 서서 각자 막춤을 추다가, 가운데 있는 친구를 www.acmicpc.net 저는 dfs를 통해 문제를 해결하였습니다. dfs를 진행하면서 해당 뎁스의 친구와 다른 친구와 같이 춤을 추게 맺어주고, 총 맺어진 친구의 수를 구하였습니다. 여기서 아무도 친구 관계가 아니라면, 혼자 올라갈 수 있기 때문에 result = 1로 초기화하였습니다. 마지막으로 총 맺어진 친구의 수가 n보다 작다라는건 센터에 아무도 친구로 맺어지지 않은 친구를 세울 수 있기 때문에 하나 증가시켜서..

https://www.acmicpc.net/problem/25516 25516번: 거리가 k이하인 트리 노드에서 사과 수확하기 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 모든 간선의 길이는 1이다. 트리 T의 각 정점에는 사과가 0개 또는 1개 놓여있다. 루 www.acmicpc.net 저는 bfs를 통해 문제를 해결하였습니다. 평소 bfs에서는 방문 체크를 하지만, 트리이기 때문에 사이클이 존재하지 않아 방문 체크를 진행하지 않았습니다. 저는 time을 통해 해당 노드의 깊이를 확인하였고, time이 k를 넘어가면 탐색을 끝내도록 하여 문제를 해결하였습니다. package BOJ.bfs; import java.io.Buff..

https://www.acmicpc.net/problem/1246 1246번: 온라인 판매 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다. www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. 먼저 P를 오름차순으로 정렬하였습니다. i번째 사람은 P[i]이하의 가격에 사기 때문에 오름차순 정렬하고 순차적으로 접근하게 된다면, P[i]의 가격으로 뒤에 있는 사람들은 모두 사고, 앞에 있는 사람들은 안 사기 때문입니다. P[i] * (m-i)의 공식이 완성됩니다. 또한, 달걀의 개수가 n이기 때문에 m-i가 아무리 커도 n보다 커지면 안됩니다. 즉,..

https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 저는 bfs를 통해 문제를 해결하였습니다. bfs를 통해 탐색을 진행하고, 이 값이 e와 같으면 해당 시간을 리턴하여 결과값을 구하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..