Jutudy

https://www.acmicpc.net/problem/9625 풀이 첫 글자는 A로 시작합니다. 그리고 버튼을 한 번씩 누를 때 마다, 모든 A는 B로 바뀌고, 모든 B는 BA로 바뀌게 됩니다. 1) A -> B 2) B -> BA 위 두 작업은 순차적으로 수행되는 것이 아니고, 병렬적으로 수행됩니다. 코드는 순차적으로 작성하긴 해야하는데 병렬적으로 수행되도록 구현하려면, 다음 상태 (A', B'라고 칭함) 변수를 지정하면 됩니다. 1) A -> B' 2) B -> B'A' 위와 같이 표현하면 이전 A, B값이 서로 영향을 주지 않고 다음 값을 나타낼 수 있게됩니다. 예시 ABA -> B'B'A'B' (BBAB) 버튼 누르기 전 : A(..

https://www.acmicpc.net/problem/17144 풀이 매 초마다 순서대로 동작을 진행한다. 미세먼지 확산 공기청정기 작동 1. 미세먼지 확산 r x c 배열에 퍼져있는 미세먼지들은 동시에 확산된다. 동시에 확산되기 때문에, (r,c) 위치에 있는 미세먼지는 인접한 네 방향으로 미세먼지를 확산시킴으로서 자신의 남은 미세먼지양은 줄게되고, 동시에 인접한 네 방향으로부터 확산된 미세먼지의 양이 추가된다. -1 10 20 -1 5 6 위와 같은 모양으로 미세먼지가 존재한다고 했을 때 (-1은 공기청정기), (0,1) 위치의 미세먼지가 인접한 네 방향으로 2만큼의 미세먼지를 확산시키고, 자산의 미세먼지 양은 -4만큼 감소한다. -1 10 - 4 20 + 2 -1 5 + 2 6 그리고 동시에, ..

https://www.acmicpc.net/problem/15686 풀이 0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2 위의 예제를 보자. 집의 개수 : 6개 치킨집(가게)의 개수 : 2개 각각의 집은 치킨거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합니다. 각 집에서 모든 치킨집까지의 최단 거리를 각각 구할 수 있다. 이 중 가장 가까운 곳에 있는 치킨집까지의 거리가 해당 집의 치킨거리가 되는 것이다. 위의 예제에서 (0,1)의 집에서부터 한 번의 BFS(DFS도 가능)을 수행하면 모든 치킨집까지의 최단 거리를 구할 수 있다. 이런 식으로 각 집의 위치를 시작점으로 BFS를 수행(집의 개수만큼 BFS수행)하게되면, 모든 집에서부터 모든 치킨..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 수빈이의 현재 점에서부터 BFS를 시작한다. 갈 수 있는 경우는 (X-1, X+1, 2*X) 3가지 경우이다. 가장 빠른 시간을 찾는 문제이기 때문에 이미 방문한 위치를 또 방문하는 경우에는 다시 큐에 넣지 않는다. [소스코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOExce..

www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [풀이] 1. N명 중 N/2명을 골라서 팀을 짠다. - 조합 - 비트마스킹으로 구현했는데 그냥 배열로 해도 속도 차이 없을 것 같다. 2. 1번에서 만든 팀과 나머지 인원 팀의 능력치 합을 각각 구하고, 두 능력치의 차이를 구한다. 인풋으로 주어지는 2차원 배열 arr를 모두 탐색하면서 i,j가 팀에 속할 경우 arr[i][j] 값을 능력치 합에 더하면 된다. 3. 1~2번을 반복하여 두 팀의 능력치의 차이의 최소값을 구한다. [..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net [풀이] ​ BFS 문제이다. ​ 바깥 부분이 공기이기 때문에 바깥 부분에서 BFS를 진행하면 공기와 맞닿은 치즈를 찾을 수 있다. ​ 공기와 맞닿은 치즈 부분을 찾은 뒤 그 부분을 공기로 바꾸고 바뀐 치즈의 개수를 카운트하면서 치즈가 남지 않을 때 까지 반복하면 된다. ​ 공기(0,0)에서 BFS 진행 공기 공기 공기 공기 공기 공기 치즈 치즈 치즈 공기 공기 치즈 빈칸 치즈 공기 공기 치즈 치즈 치즈 공기 공기 ..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B public static void main(String[] args) ..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] ​ ​ 기본적인 BFS 문제라고 생각하고 접근했다. 단순히 아래, 대각선 아래, 오른쪽 방향으로만 이동하기 때문에 visit 체크를 따로 해줄 필요도 없었고, (N,N) 까지 갈 수 있는 모든 경로를 구하기만 하면 되서 BFS를 돌며 파이프 앞부분이 (N,N)에 도달할 때 마다 count를 ++해주었다. 결과는 잘 나왔지만, 시간초과가 났다. ​ ​ < 동적 프로..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] ​ 깡(?) 시뮬레이션 문제이다. ​ K년 만큼 for문을 돌리면서 1년마다 봄, 여름, 가을, 겨울에 수행해야 할 일들을 순차적으로 실행한 뒤에 남아있는 나무의 수를 구하면 된다. ​ 여기서 가장 중요한 점은 나무를 우선순위 큐로 관리하는 것이다. ​ 시기에 나이가 어린 나무부터 양분을 먹거나 죽어야 하기 때문에 우선순위 큐에 나이 기준 오름차순으로 나무를 넣어준다. ​..

https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [풀이] ​ DP문제. ​ 길이를 1부터 N까지 1씩 늘리면서 만들어진 계단 수의 맨 뒤에 숫자를 추가해주는 방법으로 경우의 수를 구해준다. ​ ex) N=10일 때 계단 수는 9876543210 이다. 여기서 N=11인 계단수를 구할 때는 9876543210 의 맨 뒤 수인 0과 1 차이나는 1을 추가해준다. 그러면 98765432101 이라는 수가 만들어진다. ​ 만들어져있는 계단 수의 앞 또는 중간에 수를 붙이려고 하면 머리도 복잡해지고 가장 중요한 문제는 만들어진 수의 중복이 발생하는 경우가 생긴다. ​ 그래서 ..