박카스러버

https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 저는 해당 문제를 프림 알고리즘을 통해 해결하였습니다. 프림 알고리즘에서 i가 2보다 클때부터 i*t를 더 해주어 정복했을 때 t비용이 증가하는 것을 구현하였습니다. package BOJ.MST; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Array..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 저는 해당 문제를 DP와 BFS를 이용해 문제를 해결하였습니다. 처음에는 boolean으로 방문체크를 함으로써 96퍼센트에서 시간초과가 나왔습니다. 다음으로는 DP를 이용해 해당 노드에 어떤 최소 시간때에 도착하였는지를 확인하였고, 만약 이 노드가 현재시간보다 +1보다 크다면 break해 해당 방향 탐색을 종료해 시간을 단축시켰습니다. package BOJ.BFS; import java..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 저는 해당 문제를 BFS를 이용하여 문제를 해결하였습니다. 각각의 회원에서 모든 회원을 BFS로 방문하는데 걸리는 시간을 통해 해당 회원의 점수를 계산하였습니다. 각각의 회원에서 모두 점수를 확인하고 가장 낮은 점수와 같은 점수를 가진 회원들을 출력하였습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io.InputStreamRea..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 저는 해당 문제를 슬라이딩 윈도우 개념을 활용하여 문제를 해결하였습니다. 저는 인덱스를 변화하는 전구의 맨 앞의 것을 잡았습니다. 문제에서 i를 저는 i-1로 잡았습니다. 이렇게 잡은 이유는 이렇게 설정하면 뒤의 행동이 앞의 상태를 변경하지 않게됩니다. 즉, i에서의 행동이 i이전의 배열에 영향을 주지 않습니다. 문제는 문제에서의 맨 앞의 전구를 키는 것은 어떻게 설정..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 해당 문제는 일반적인 BFS문제랑 문제 접근이 달라서 아이디어를 생각하기 힘들었습니다. 먼저 조합을 통해 학생들을 7명을 뽑습니다. 그 중 S가 4이상인지 확인하고 DFS를 통해서 각각의 뽑은 친구들이 연결되어 있는지 확인하였습니다. 저는 다음과 같이 1차원 배열로 해당 학생의 위치를 저장하였습니다. (0,0) -> 0 = 0 (1,1) -> 1*5 + 1 = 6 친구들이 연결되어있는지는 아무 학생을..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 저는 해당 문제를 BFS를 이용하여 문제를 해결하였습니다. 하지만 문제의 내용을 그대로 코드로 짜게 된다면 시간 초과가 나오게 될 것입니다. 그래서 저는 문제를 반대로 생각하였습니다. T(긴 문자열)에서 S(짧은 문자열)로 만들수 있는지를 BFS로 코드를 작성하였습니다. S에서 T로 BFS코드를 작성하는 경우, 추가하는 조건만 있기 때문에 점점 많은 문자열..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 저는 해당 문제를 재귀를 이용하여 문제를 해결하였습니다. 문제를 부분적으로 나눠본다면 1에서 맨맽의 원반을 제외한 원반들을 2로 옮기고 맨 밑의 원반을 3으로 옮기고 2에 있는 원반들을 3으로 옮겨야합니다. 즉 from(1)에서 mid(2)로 맨밑을 빼고 전부 옮기고 from(1)에서 to(3)으로 맨밑의 것을 옮기고 다시 mid(2)에서 to(3)으로 2에 존재하는 모든 원반들을 옮..

https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 저는 해당 문제를 Queue를 이용하여 문제를 해결하였습니다. 가장 밖에 있는 라인부터 안쪽으로 Queue를 이용해 같이 돌아야하는 요소들을 모두 집어넣습니다. 이후 돌아야 되는 만큼 Queue 앞에서 빼서 뒤에 넣습니다. 이때 k를 Queue 사이즈로 모듈러 연산을 합니다. k가 Queue사이즈만큼 돌..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 저는 해당 문제를 union find set을 이용하여 문제를 해결하였습니다. 처음 이야기를 아는 사람끼리 그룹으로 묶었습니다. 각각의 파티의 사람들을 한 그룹으로 만들었습니다. 마지막으로 각 파티의 한사람과 처음 이야기를 아는 사람 중 한사람의 그룹을 비교해서 둘의 그룹이 다르다면 파티에서 과장할 수 있기 때문에 결과값을 하나 올려주었습니다. package BOJ.ETC; import java.io.Buf..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 저는 처음에 2중 for문으로 문제를 해결하려 하였습니다. 하지만 n의 최대가 100,000여서 시간 초과가 나왔습니다. 다음으로는 투 포인트를 생각하였습니다. 처음과 끝을 가리키게 하고 둘 중 절대값이 큰 값의 인덱스를 줄여나가면서 절대값 합이 최소인 것을 찾아 나갔습니다. 저는 가장 낮은 값과 가장 큰 값을 더해가면서 가장 낮은 값을 올리고 가장 큰 값은 줄이는 방식을 생각하였습니다. 그..