본문 바로가기

Algorithm14

[백준] 낚시 30461번 Python 문제 건덕이는 일감호에 딸린 작은 섬, 와우도에 앉아 세월을 낚아 올리는 중이다. 일감호는 N*M 공간으로 나타낼 수 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있고, 각 칸에는 물고기가 여럿 존재한다. 가장 수심이 깊으면서 건덕이로부터 가장 먼 칸은 (N, M)이다. 건덕이는 낚싯대를 휘둘러 원하는 칸에 미끼를 던질 수 있다. 무게가 a인 무게추를 매달아 b만큼의 힘으로 낚싯대를 휘두르면 (a, b) 칸에 미끼가 존재하게 된다. 미끼는 일감호 공간 안에서 물고기들을 사로잡는데, 그 대상은 미끼가 속한 칸으로부터 수면까지 존재하는 모든 칸에 있는 물고기들이다. 즉, (a, b)에 존재하는 미끼는 1≤ i ≤ a인 모든 정수 i에 대해서 (i, b)$에 존재하는 모든 물고기를 사로잡는다. 건덕이.. 2024. 1. 16.
[백준] 십자카드 문제 2659번 Python 문제 위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다. 모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다. 입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오. 예를 들어서, 다음과 같은 십자 카드의 시계수는 1122이며, 이 시계수보다 작.. 2024. 1. 12.
[백준] 옥상 정원 꾸미기 6198번 Python 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12 2 -> 빌딩의 높이 [1][2][3][4][5][6] -> 빌딩의 번호 1번 관리인은 2, 3, 4번 빌딩의.. 2024. 1. 11.
[백준] 트리의 부모 찾기 11725번 Python 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 출처 문제를 만든 사람: baekjoon 잘못된 조건을 찾은 사람: jh05013 ! 문제 생각&풀이 ! 각 노드의 부모 노드 번호를 찾아가야하므로 깊이가 어느정도인지 찾아야한다고 생각했기에 DFS를 활용한 탐색으로 문제를 풀어보면 어떨까부터 생각을 했다. 우선은 간선 정보 입력을 양방향 연결로 받아서 arr에 각 정점의 연결된 정점들을 담아.. 2024. 1. 11.
[백준] 치킨 배달 15686번 Python 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지.. 2024. 1. 8.
[백준] 토마토 7569번 Python 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한.. 2024. 1. 8.

티스토리툴바