BOJ
-
백준(BOJ 1300) K번째 수알고리즘 풀이/백준(Boj) 2020. 2. 7. 17:49
제목 : https://www.acmicpc.net/problem/1300 1300번: K번째 수 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 : 임의의 숫자 mid를 통해 K 번째 숫자인지 확인해보자 이때 순차적 탐색은 n이 10만 이므로 이분 탐색을 통해 해결하였다. 후보들은 모두 i*j 값이기 때문에 i의 배수들이고 min(mid/i, N)이 i번째 행에서 mid보다 작은 숫자들의 개수가 된다.
-
백준(BOJ) 17825번 주사위 윷놀이알고리즘 풀이/백준(Boj) 2020. 1. 23. 02:32
문제: https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다. 게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에 www.acmicpc.net 풀이: 윷놀이 판을 2차원 배열로 나타내 보았다. 이때 서로 이어질 수 있게 만들어 주고 방향을 표시하는 d 배열도 따로..
-
백준(BOJ) 16974번 레벨 햄버거알고리즘 풀이/백준(Boj) 2020. 1. 18. 14:45
문제 : https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1) 예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티) 상도가 상근날드에 방문해서 레벨-N 버거를 시켰 www.acmicpc.net 풀이 : 우선 hb [n] 은 n번째 레벨의 전체 재료의 수고 p [n] 은 p번째 레벨의 패티 수로 각 레벨의 전체 재..
-
백준(BOJ) 16957번 체스판 위의 공알고리즘 풀이/백준(Boj) 2020. 1. 16. 14:09
문제 : https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다. 인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다. 그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다. 공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을 www.acmicpc.net 풀이 : 각각의 좌표는 8방향을 탐색하면서 가장 작은 좌표를 찾는다. 그리고 가장 작은 좌표를 부모 좌표로 나타낸다...
-
백준(BOJ) 17090번 미로 탈출하기알고리즘 풀이/백준(Boj) 2020. 1. 16. 03:15
문제 : https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 www.acmicpc.net 풀이 : 기본적으로 방문을 시작했을 때 ret = 0으로 두어서 방문할 수 없는 상태를 만든다. 이는 사이클으로 무한루프..
-
백준(BOJ) 17088번 등차수열 변환알고리즘 풀이/백준(Boj) 2020. 1. 12. 13:47
문제 : https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다. 수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가 www.acmicpc.net 풀이 : 모든 경우를 다해 보기에는 N이 10만이기 때문에 3^10만으로 도저히 불가능하다. 따라서 등차수열의 성질을 ..
-
백준(BOJ) 16954번 움직이는 미로 탈출알고리즘 풀이/백준(Boj) 2020. 1. 7. 14:33
문제 : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 www.acmicpc.net 풀이 : 시간이 8초부터는 벽은 모두 내려간 상태고.(점)만 남은 상태가 된다. 이 상태에서는 무조건 목표지점(0..
-
백준(BOJ) 매직 스퀘어로 변경하기알고리즘 풀이/백준(Boj) 2020. 1. 1. 16:43
문제 : https://www.acmicpc.net/problem/16945 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자. 5 3 4 1 5 8 6 4 2 이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 www.acmicpc.net 풀이 : 1. 가로 세로 3 3 은 편의를 위해 1차원 배열로 바꾸어 풀었다. 매직 스퀘어는 1~9가 중복되지 ..