분류 전체보기
-
백준 3190번 뱀알고리즘 2023. 4. 13. 10:16
문제 설명 이번 문제는 Dummy라는 도스게임을 제작하는 문제입니다. N * N 정사각 보드위에서 뱀이 매 초마다 아래와 같은 규칙으로 움직이고 사과의 위치와 뱀의 이동경로가 주어질 때, 게임이 몇 초에 끝나는지 계산하는 문제입니다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킵니다. 만약 이동한 칸에 사과가 있다면 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않습니다. 문제 풀이 0. 변수 N=int(input()) # 보드의 크기 K=int(input()) # 사과의 개수 apples=[list(map(int,input().split())) for _ in range(K)] # 사과의..
-
백준 13460 구슬 탈출 2알고리즘 2023. 4. 12. 10:32
문제 설명 이번 문제는 보드 안에 빨간색 파란색 구슬이 한 개씩 있고 기울일 수 있는 최대 횟수가 주어질 경우, 해당 횟수 내에 빨간 구슬을 먼저 구멍에 빠질 수 있다면 해당 기울인 횟수를 구하는 문제입니다. 구슬은 손으로 건드릴 수 없고, 중력을 이용해 왼쪽 오른쪽 위 아래로 기울여서 구슬을 움직여야합니다. 기울이는 동작은 구슬에 벽에 닿아 움직이지 않을 때까지만 합니다. 빨간 구슬과 파란 구슬은 한 칸안에 있을 수 없습니다. 빨간 구슬이 구멍에 빠진 뒤 해당 턴에 파란 구슬도 구멍에 빠지면 실패입니다. 문제 풀이 아이디어 브루트 포스 이번 문제는 구슬의 움직임에 따라 빨간 구슬 파란 구슬의 움직임을 모두 확인해야 하므로, 모든 경우의 수를 고려하는 브루트 포스 방법을 생각했습니다. 고려해야 하는 점 ..
-
백준 25515번 트리 노드 합의 최대값알고리즘 2023. 4. 3. 10:34
문제 설명 이번 문제는 트리가 주어지고 노드마다 하나의 정수가 적혀있을 때, 루트 노드에서 시작해 이웃한 노드를 방문하여 방문한 노드에 적혀있는 정수 합의 최대값을 출력하는 문제입니다. 문제 풀이 아이디어 각 노드에서 연결된 서브 트리에서의 최대값 찾기 루트 노드로부터 트리의 형태가 주어졌으므로, 루트노드와 연결된 각 서브트리에서 노드의 정수값을 더했을 때의 최대값을 구해줍니다. 한 노드에서 자신의 자식으로부터 얻어진 정수의 최대값을 알면 해당 서브트리에서 정수 합의 최대값을 구할 수 있습니다. 그러므로, 각 노드마다 자식으로부터 얻어진 정수합의 최대값과 자신의 정수값과의 합이 최대가되도록 해줍니다. 풀이 서브트리 정수합의 최대값 구하기 재귀를 이용하여 각 노드의 자식 노드를 탐색합니다. 각 노드가 le..
-
백준 20035번 이동하기5알고리즘 2023. 3. 31. 11:11
문제 설명 이번 문제는 N*M크기의 미로가 주어지고 (i,j)에 Ai * 10^9 + Bj 개의 사탕이 놓여져 있을 때, (1,1)에서 출발하여 (N,M)으로 이동하면서 얻을 수 있는 사탕 개수의 최대값을 구하는 문제입니다. (r,c)에서 이동할 수 있는 칸은 (r+1,c), (r,c+1)입니다. 문제 풀이 아이디어 최대값을 갖는 방법 행과 열에 따라 사탕의 개수가 달라지게 됩니다. 그리고, 행에 의해 구해지는 사탕의 개수는 10^9를 곱하기 때문에 Ai(행의 사탕개수)가 큰 곳을 많이 지나다녀야 됩니다. 이동 방법 (가장 큰 Ai를 Amax, 가자 큰 Bi를 Bmax라 하겠습니다) Ai 중 가장 큰 값이 한 개일 경우 해당 행을 무조건 1열부터 지나가는 경로 하나만 있으면 됩니다. 열에 해당한 B1이 ..
-
백준 27231번 2023년이 기대되는 이유알고리즘 2023. 3. 30. 15:46
문제 설명 이번 문제는 정수 n이 주어졌을 경우, n의 자리수 사이사이에 0개 이상의 +기호를 넣어서 계산했을 때, 그 값이 각 자리수를 m제곱한 수들의 합과 같아지는 m의 개수를 구하는 문제입니다. 문제 풀이 아이디어 조합 n의 자리수 사이사이에 +기호가 들어갈 수 있는 경우의 수를 구할 경우 조합을 사용합니다. 이분 탐색 자리수 사이사이에 0개 이상의 +기호를 넣어서 계산한 값과 각 자리수를 m제곱한 합 중 같은 값이 있는지 비교할 경우 두 배열을 모두 순회하면서 값을 비교하는 것은 너무 많은 시간이 걸리므로, 이분탐색을 이용해 서로 같은 값이 있는지 비교해줍니다. 풀이 0과 1 각 자리수가 0 혹은 1만 존재할 경우, 해당 숫자의 m의 개수는 무한히 많아지므로 'Hello, BOJ 2023!'을 출..
-
백준 26124번 조명 배치알고리즘 2023. 3. 8. 10:30
문제 설명 이번 문제는 격자 칸에 조명을 배치할 경우 아래와 같은 규칙으로 각 격자칸의 영향력이 정해질 경우, 각 칸의 영향력이 정해진 격자칸이 주어졌을 때 필요한 조명의 최소 개수를 구하는 문제입니다. (해당 격자칸으로 조명 배치를 만들 수 없을 경우 -1 출력) 조명 L의 밝기가 c일 경우 L이 각 빈칸에 미치는 영향력은 다음과 같이 계산된다. L이 위치한 격자칸에 미치는 영향력은 c이다. L과의 거리가 1인 격자칸에 미치는 영향력은 c-1이다. … L과의 거리가 c-2인 격자칸에 미치는 영향력은 2이다. L과의 거리가 c-1인 격자칸에 미치는 영향력은 1이다. 그 외의 빈칸에는 영향력을 미치지 않는다. 어떤 빈칸에 영향을 미치는 조명의 개수가 2개 이상인 경우, 이 빈칸의 영향력은 영향을 미치는 조..
-
백준 23978번 급상승알고리즘 2023. 3. 7. 13:10
문제 설명 이번 문제는 효석이가 자신이 정한 N개의 날짜에 코인을 X원으로 급상승시키고 처음 코인 가격이 오른 날부터 한 개씩 매도할 때, K원 이상 현금화할 수 있는 가장 작은 정수 X를 구하는 문제입니다. (단, 코인이 X원으로 오른 뒤 하루에 1원씩 0원이 될 때까지 가격이 낮아진다.) 문제 풀이 아이디어 X를 알 때 최종 현금화할 수 있는 금액을 구하는 방법 정해진 N개의 날짜에 코인이 X원 상승한 뒤, 하루에 1원씩 작아집니다. 여기서, 코인이 급상승하는 날짜 사이의 일 수가 X보다 크다면 코인은 0원까지 떨어지게 될 것이고, 코인이 급상승하는 날짜 사이의 일 수가 X보다 작다면 코인은 X-{코인이 급상승하는 날짜 사이의 일수 } 까지만 떨어지게 됩니다. 이분 탐색 문제에서 주어진 N,K(1
-
백준 17251번 힘 겨루기알고리즘 2023. 3. 6. 10:42
문제 설명 이번 문제는 N명의 참가자들을 나열하고 기준선을 통해 팀이 나눈 다음 각 팀에서 가장 힘쎈 사람이 나왔을 때, 둘 중 더 힘 쎈 사람이 이기게 됩니다. N 명의 참가자의 힘을 나타내는 정수가 주어질 때, 이길 확률이 더 높은 팀을 구하는 문제입니다. 문제 풀이 아이디어 가장 힘 쎈 팀 구하는 방법 기준선이 어디에 있는지에 상관없이 항상 가장 힘이 갖아 쎈 사람이 있는 팀이 이기게 됩니다. 가장 힘이 쎈 사람이 한 명일 경우 가장 힘이 쎈 사람의 인덱스를 i라하면, 기준선이 1~i-1일 경우 블루팀이 이기고, i~N-1일 경우 레드팀이 이기게 됩니다. 여기서 두 팀이 이길 확률을 구해보면, 블루팀은 (i-1)/N이고 레드팀은 (N-i)/N입니다. 그러므로 두 팀 중 이길 확률이 높은 팀은 i-1..