본문 바로가기

BOJ67

[BOJ] 2583. 영역 구하기(Python) / BFS www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 22분 소요 아주 간단한 BFS 문제 M*N크기 맵 1로 초기화 Input 받은 내용을 미리 M*N크기의 맵에 0으로 그려줌 이후 맵에서 1일 때 연결된 곳 BFS 이용하여 0으로 지워주면서 갯수 셈 연결된 곳 0으로 지우는 작업 끝날 때마다 resut += 1, parts에는 갯수 append 해주고, 마지막 출력할 때 sort 파이썬 코드는 다음과 같다. import sys input.. 2021. 3. 4.
[BOJ] 2485. 가로수(Python) www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수 www.acmicpc.net gcd(Greatest Common Devisor) 최대공약수 구하는 함수 이용해서 148ms로 시간 단축 => 통과 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline from math import gcd n = int(input()) trees = [] gaps = [] for i in range(n): trees.append(int(input())) if i.. 2021. 3. 4.
[BOJ] 9095. 1, 2, 3 더하기(Python) / DP www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 처음에 combination으로 풀려다가 숫자를 자세히 보니 규칙성 발견 => DP로 접근해보자 4번째 수 이후로 이전의 세 수의 합의 값을 가짐. n은 10까지 수를 가지므로 미리 리스트로 만들어놓는다. 인덱스에 해당하는 값을 찾아 간단하게 풀 수 있는 문제. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline dp = [1, 2, 4] for i in range(3, 12): dp.append(dp[i-3]+dp[i-2]+dp[i-1]) # print(dp) n.. 2021. 3. 4.
[BOJ] 2468. 안전 영역(Python) / BFS www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어렵지 않은 BFS 문제였다. 실제로 난이도 실버1. 기본적인 BFS 틀에 조건만 이동할 위치를 현재 비의 양과 비교해 더 높을 때마다 BFS를 확장시켰다. 이 때, 비의 양이 달라질 때마다 경우가 달라지므로 나름의 아이디어를 내서 visited를 재활용하기 위해 새로 방문 표시를 할 때는 현재 비의 양으로 표현해 비의 양이 다른 경우와 구분했다. 비의 양을 결정한 후 결과(안전영역의 갯수, temp)가 나올 때마다 .. 2021. 2. 25.
[BOJ] 2456. 나는 학급회장이다(Python) www.acmicpc.net/problem/2456 2456번: 나는 학급회장이다 첫째 줄에는 반의 학생들의 수 N (3 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 각 줄에는 각 학생이 제출한 회장후보 3명에 대한 선호 점수가 주어지는 데, 첫 번째 점수는 후보 1번에 대한 점수이고 두 www.acmicpc.net 브론즈 1 문제이다. 단순 하드코딩으로 이차원 배열에 3명의 후보별로 [총점, 3점, 2점] 리스트로 구성해 정렬하는 방식으로 풀다가 막혀서 구글링하다가 3점, 2점 점수 합 제곱을 해줘서(가중치 처리) 크기 비교를 하는 풀이법을 찾았다. (이런 아이디어 나도 내고 싶다..) 아이디어를 참고해 풀었다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.rea.. 2021. 2. 24.
[BOJ] 4179. 불! (Python) / BFS www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 전형적인 최단거리 구하기 BFS 문제이다. 처음 아이디어는 사람이 먼저 4방향으로 뛰고, 불을 퍼트리고, 사람 이동, 불 이동 이런 식으로 번갈아 해줬는데 어디서 꼬였는지 자꾸 70%대에서 계속 틀렸다. 3번 넘게 계속 틀렸습니다가 떠서 질문검색을 통해 1. 불을 먼저 완전히 퍼트리고 이 정보를 보고 2. 사람이 격자 밖으로 나갈 수 있는지 여부를 확인함을 알았다. 불이 각 위치에 도달한 정보를 .. 2021. 2. 24.

티스토리툴바