[BOJ] 19939. 박 터뜨리기 (python)

✏️ 문제 K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다. 우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다. 게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다. 공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다. N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.각..

• format_list_bulleted Algorithm/BOJ
• · 2023. 5. 1.
• textsms

[BOJ] 17298. 오큰수 (python)

✏️ 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 🤖 알고리즘 #스택 🤯 풀이 방법 마지막 인덱스부터 거꾸로 탐색하며 최대값을 저장한다. 위에서부터 차례로 꺼내며 더 큰 값을 찾으면 그 값이 오큰수 현재 인덱스..

• format_list_bulleted Algorithm/BOJ
• · 2023. 4. 28.
• textsms

[BOJ] 15686. 치킨 배달 (python)

✏️ 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같..

• format_list_bulleted Algorithm/BOJ
• · 2023. 4. 23.
• textsms

[BOJ] 2828. 사과 담기 게임 (python)

✏️ 문제 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M end: g = abs(cur - end) ans += g end = cur start += g print(ans) https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M

• format_list_bulleted Algorithm/BOJ
• · 2023. 4. 13.
• textsms

[BOJ] 1058. 친구 (python)

✏️ 문제 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다. [입력] 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다. [출력] 첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다. 🤯 풀이 방법 ..

• format_list_bulleted Algorithm/BOJ
• · 2023. 4. 10.
• textsms

[BOJ] 13023. ABCDE (python / java)

✏️ 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 🤖 알고리즘 #그래프 #백트래킹 🤯 풀이 방법 친구 관계를 가진 A, B, C, D, E가 있냐는 말인데, 그냥 그래프를 순회해서 다섯 단계까지 갈 수 있냐는 뜻이다. 자바로 생각할 때는 금방 풀어서 구현했는데 몇 주 뒤에 파이썬으로 하려니 시간초과 나고 난리도 아니었다. 일단 그래프 관계를 리스트로 만들고, 함수를 만들어서 ..

• format_list_bulleted Algorithm/BOJ
• · 2023. 4. 9.
• textsms