본문 바로가기
728x90

알고리즘316

[python] 백준 2631 줄세우기 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 해결 LIS (Long Increase sequence) 구하는 문제 가장 긴 증가하는 수열이 만들어 진 부분 수열을 구한다음 그 원소들을 빼고 나머지를 필요한 곳으로 옮기면 되는 것이다. CODE import sys input = sys.stdin.readline n = int(input()) A = [0]+[int(input()) for _ in range(n)] dp = [0 for _ in .. 2023. 3. 20.
[python] 백준 15683 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해결 문제가 많이 어려웠다.(다른 분들의 풀이를 참고했다.) 결국 cctv 종류당 이동할 수 있는 방법의 수가 정해져 있기 때문에 dfs, bfs를 이용한 완전탐색을 해야한다. 이 사실을 알고 cctv당 이동 할 수 있는 방법을 리스트 안에 구현을 하면 사실 끝이다. 완전 탐색 후 가장 적게 사각지대가 생긴 개수를 구하면 된다. CODE import sys input = sys.s.. 2023. 3. 19.
[python] 백준 1057 토너먼트 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 문제 해결 사실 계속 이기다보면 어디서든 만나기 때문에 붙기전에는 무조건 이긴다는 가정하에 -1이 나올일은 없다. (cnt)라운드 (i)조 경기를 치른다고 할 때 다음에는 (cnt+1)라운드 ((i-1)//2 + 1)조 경기를 치룬다. 따라서 처음에 a조 b조의 번호를 받았을 때 나중에 같은 번호가 되는 라운드를 출력하면 된다. CODE import sys input = sys.stdin.readline.. 2023. 3. 19.
[python] 백준 2468 안전 영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 해결 문제를 이해하는 것 부터 어렵다. 물에 잠기는 높이는 정해지지 않았다. 물의 높이가 i일 때 잠기지 않는 영역의 개수를 구할 수 있다. 물의 높이를 바꿔가며 잠기지 않는 영역의 최대 개수를 구하는 것이다. 물의 높이는 0부터 (가장 높은 지역 -1) 까지 차례로 고정하고 문제를 해결할 것이다. 영역의 개수를 구하는 것은 bfs()의 단골 문제이다. visited를 이용해서 영역의 개수를 구하면.. 2023. 3. 19.
728x90