자료구조
-
[백준] 20438 출석체크 with PythonPS 2022. 6. 5. 16:01
📌 BOJ 20438 출석체크 💡 조건 학생들은 접속 순서대로 3번부터 N + 2번까지 입장 번호를 받게 된다. 지환이가 한 학생에게 출석 코드를 보내게 되면, 해당 학생은 본인의 입장 번호의 배수인 학생들에게 출석 코드를 보내어 해당 강의의 출석을 할 수 있게끔 한다. 하지만, K명의 졸고 있는 학생들은 출석 코드를 제출하지 않고, 다른 학생들에게 보내지 않는다. 지환이는 무작위로 한 명의 학생에게 출석 코드를 보내는 행위를 Q번 반복한 뒤, 출석부 정리를 위해 특정 구간의 입장 번호를 받은 학생들 중에서 출석이 되지 않은 학생들의 수를 구하고 싶다. 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤..
-
[백준] 20166 문자열 지옥에 빠진 호석 with PythonPS 2022. 6. 4. 01:36
📌 BOJ 20166 문자열 지옥에 빠진 호석 💡 조건 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다. 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자. 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다. 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이..
-
[백준] 17485 진우의 달 여행 (Large) with PythonPS 2022. 6. 4. 01:03
📌 BOJ 17485 진우의 달 여행 (Large) 💡 조건 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. N, M (2 ≤ N, M ≤ 1000), 각 행렬의 원소값은 100 이하의 자연수이다. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다. 진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다. 최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산하는 문제 다이나믹 프로그래밍, 완전탐색 유형의 문제 🖥 소..
-
[백준] 13459 구슬 탈출 with PythonPS 2022. 6. 3. 02:29
📌 BOJ 13459 구슬 탈출 💡 조건 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. N, M (3 ≤ N, M ≤ 10) 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 각각의 동작에서 공은 동시에 ..
-
[백준] 3151 합이 0 with PythonPS 2022. 6. 1. 01:22
📌 BOJ 3151 합이 0 💡 조건 1 ≤ N ≤ 10000 -10000 ≤ Ai ≤ 10000 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다. 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라. N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하는 문제. 이분 탐색, 투 포인터 유형의 문제 🖥 소스 코드 from sys import stdin # 이분탐색 n = int(stdin...
-
[백준] 2637 장난감 조립 with PythonPS 2022. 6. 1. 00:37
📌 BOJ 2637 장난감 조립 💡 조건 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다. 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장난감 완제품을 조립하기 위해 필요한 기본 부품의 종류별 개수를 계산하는 문제. 자연수 N(3 ≤ N ≤ 100), 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 자연수 M(3 ≤ M ≤ 100)이 주어지고, 그 다음 M개의 줄에는 어떤 부품을 ..
-
[백준] 2342 Dance Dance Revolution with PythonPS 2022. 5. 20. 20:50
📌 BOJ 2342 Dance Dance Revolution 💡 조건 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자. 처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다. 두 발이 같은 지점에 있는 것이 허락되지 않는다. 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다. 발을 이동할 때 힘을 사용하게 된다. 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. 반..
-
[백준] 18291 비요뜨의 징검다리 건너기 with PythonPS 2022. 5. 20. 20:25
📌 BOJ 18291 비요뜨의 징검다리 건너기 💡 조건 징검다리는 비요뜨가 있는 방향에서부터 반대 방향까지 차례로 1번, 2번, ..., N번의 번호를 가지고 있다. 비요뜨는 1번 징검다리 위에 올라갔다. 그리고 아래 두 가지 규칙을 지키며 징검다리를 건너려고 한다. 1 ≤ X ≤ N 인 임의의 정수 X에 대해, 현재 있는 징검다리의 번호를 i번이라고 할 때 i+X번 징검다리로 뛸 수 있다. N번째 징검다리를 지나쳐선 안 되고, 정확히 도착해야 한다 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 1000) 각 테스트 케이스는 한 줄로 구성되며, 징검다리의 개수를 의미하는 N이 주어진다. (1 ≤ N ≤ 109) 각 테스트 케이스에 대해, 한 줄에 하나씩 규칙을 만족하면서 징검다리를 건..
-
[백준] 17204 죽음의 게임 with PythonPS 2022. 5. 19. 01:04
📌 BOJ 17204 죽음의 게임 💡 조건 게임에 참여하는 N명의 사람들은 원탁에 둘러앉게 된다. N(3 ≤ N ≤ 150) 게임을 시작하는 사람은 0번, 그 오른쪽 사람은 1번, 그 오른쪽은 2번, N-1번의 오른쪽 사람은 다시 0번이 된다. 게임 참여자들간에 지목을 완료한 상태가 주어질때, 보성이가 벌주를 마시기 위해 록 하자. 영기가 불러야 하는 가장 작은 양의 정수 M을 보성이 몰래 귀띔해 주도록 하자. 보성이의 번호 K(1 ≤ K ≤ N - 1) 김영기는 게임을 제안하였기에 자연스럽게 0번이 된다. N줄에 걸쳐 i(0 ≤ i ≤ N - 1)번 사람이 지목하는 사람의 번호 ai(0 ≤ ai ≤ N - 1)가 주어진다. 자기 자신을 지목하는 경우도 존재할 수 있다. 영기가 말해야 하는 가장 작은 양..