친절한 도현씨 친절한 도현씨

# 그리디 알고리즘 # n의 범위가 현저히 작았다면 dfs 풀이도 가능한데 n의 범위가 너무 크다. ★ 풀이 이 문제의 주 목적은 욱제부터 공을 던지기 시작해서 마지막 사람이 받을 수 있냐 없냐이다. 결국 욱제부터 공을 던져서 욱제 오른쪽 사람들이 받으면서 마지막 사람한테 전해주면 된다. 그럴라면 어떻게 해야할까? 일단 최대 사거리로 던진다. 그리고 바로 오른쪽 사람이 받을 수 있다면 오른쪽 사람이 최대로 던진다. 그 과정에서 바로 전에 사람보다 더 멀리 던진다면 값을 갱신시켜주고 그것이 아니라면 값을 유지한다. 이 과정을 마지막 사람까지 반복해주면 된다. ★ 코드 import sys input = sys.stdin.readline n = int(input()) data = list(map(int,inp..

# 맛도리 문제였다 # 쉽지 않았다 # 그리디적인 생각 == 직관 # 누적합 여러 알고리즘이 결합된 맛있는 문제였다. 쉽지 않았고 중간에 포기할까도 생각했지만 스크롤을 내렸을 때 중등부 1번 문제인 것을 보고 더 생각을 해보기로 했다. 일단 주어지는 입력의 최대 크기는 십만이다. 마지막 테스트 케이스를 통과하기 위해서는 이 십만개의 테스트 케이스를 통과해야 한다. 문제를 읽고 단순하게 생각하기만 해 본다면 꿀벌이 위치해야 하는 위치 2곳과 꿀통이 위치해야 하는 위치를 합한 총 3곳을 조합 형태로 뽑아 경우의 수를 구하는 것에서 끝나는게 아니라 여기서 더 나아가 벌들이 위치한 곳에서부터 이동하면서 꿀을 채취해야한다. 더 나아갈 필요도 없이 3곳을 조합 형태로 뽑는 곳에서부터 시간 초과가 발생한다. 그렇다면..

와우와우와우와우와우 진짜 맛도리 문제였다. 처음에는 조합을 떠올렸으나 입력 크기를 보고 그리디를 생각했다. 하지만 그리디로 생각하기에는 말이 안되는 부분들이 많아서 dp가 아닌가 싶었다. 그런데 또 dp로 풀자니 안 돼서 알고리즘 분류를 봤다. 그리디, 누적합, 정렬이 있는 것을 보고 더 헷갈렸다. 정렬을 처음부터 하는 것은 문제에 어긋나는 것이기 때문에 안되고 그리디는 처음에 생각했던 것처럼 말이 안 됐고 남은 것은 누적합인데 평소에 ps에서 누적합의 빈도가 낮긴 했지만 그렇다고 모르는 알고리즘을 아니었지만 도대체 누적합으로도 어떻게 풀라는 것인가 k명이 교실을 선택해야 하는데 흠...... 교실 점수에 * 횟수를 막 그리디적으로 해보다가 문제에서 시키는 대로 그냥 한 명 한 명 교실을 택해서 앞으로 ..

★ 접근 센서의 개수 최대 만 + 집중국의 개수 최대 천 + 센서 좌표값 (절댓값) 백 만 + 시간 제한 2초 => 종합적으로 미뤄봤을 때 그리디 알고리즘이 떠올랐다. 근데 도대체 이것을 어떻게 그리디로 풀 것인가? 오랜 시간 생각해서 떠오른 것은 일단 데이터를 정렬하고 index가 1차이 나는 센서끼리 차이를 구해보기로 햇다. ★ 풀이 집중국을 하나 설치한다는 것은 모든 센서가 하나의 집중국과 수신한다는 얘기이다. 즉 모든 센서가 하나의 구성이다. 집중국을 두개 설치한다는 것은 센서가 두 개로 나뉘어져서 집중국과 수신한다는 얘기이다. 즉 센서가 두 구성이다. 예제 입력 1번을 예시로 들어보면 센서간의 차이가 1,2,2,3이 있다. 여기서 집중국을 두개 설치하는데 둘의 차이가 가장 적은 1을 빼면 센서는..

★ 접근 문제 지문에서 '네트워크 형태' + n과 q의 최대 크기를 미뤄봤을 때 그래프 문제인 것을 떠올렸고 처음에는 dfs로 풀었다가 시간초과가 발생했다. 입력 최대 크기가 백을 넘어가면 웬만하면 dfs를 사용하지 않는데도 불구하고 dfs를 사용했던 이유는 k,v가 입력으로 주어졌을 때 매번 v에 대해서 dfs 성질을 이용해야 된다고 생각했기 때문이다. 역시나 시간초과가 나왔고 bfs로 풀었다. ★ 풀이 코드를 보면 어이가 없을 정도로 간단하다. 매 입력에 대해서 방문하지 않은 노드이면서 현재 usado가 k보다 크거나 같다면 q에 추가(노선을 따라감) count(결과 값)를 1씩 늘린다. ★ 코드 from collections import deque import sys input = sys.stdin..

★ 접근 r,c,n의 크기가 최대 200이기 때문에 bfs로 풀까 생각했지만 폭탄이 동시에 깔리고 동시에 터지는 문제는 bfs로는 풀기 힘든 상황들이 자주 발생해서 쌩 구현을 해도 된다고 생각하고 접근 ★ 풀이 n이 1초 => 초기 상태 출력 n이 짝수 => 모든 칸이 폭탄 그 외 = > 0초 폭탄, 1초 폭탄, 2초 폭탄을 나누어서 2초를 터트리고 0초를 1초로 만들고 => 다음 1초동안 모든칸 포탄 채우고 1초 => 2초 폭탄 0초 폭탄 생성 위 구문을 n-2초 동안 반복 ★ 코드 import sys input = sys.stdin.readline r,c,n, = map(int,input().split()) graph = [list(input().rstrip()) for _ in range(r)] i..

★ 접근 모든 경우의 수를 살펴봐야하고, 엄청난 크기의 병사, 최대 백만인 라운드 수 이 요소들을 종합적으로 미루어 봤을 때 그리디 알고리즘을 떠올릴 수 있다. 근데 여기서 그리디만을 가지고는 풀 수 없다. 그리디인데도 불구하고 시간초과가 날 것이다. 우선순위 큐 알고리즘도 접목시켜야 풀 수 있다. ★ 풀이 매번 라운드 적군과 맞서 싸운다. 그러다가 아군 병사의 숫자가 적군의 병사의 숫자보다 부족할 경우 무적권을 써야한다. 이 때 무적권이 한 장도 남지 않았다면 게임을 종료시킨다. 무적권이 남아있다면 음수가 돼도 괜찮으니 현재 남은 아군 병사에 현 라운드 적군 병사의 숫자만큼 뺀다. 그리고 현재 적군 숫자를 우선순위 큐에 넣은다음 이제까지 치뤘던 전투 중 가장 적군이 많았던 숫자를 꺼낸 다음 현재 병사에..

★ 접근 - 문제 + 입력 + 예제 입력을 미루어 보았을 때 그래프 이론을 떠올렸고 dfs로 풀었다가 반례를 찾아서 bfs로 풀었다가 반례를 못 찾아서 알고리즘 분류를 보고 dp로 풀었다. 그래프 문제인데도 불구하고 dp로 풀 수 있는 이유는 물은 무조건 번호가 작은 양동이 => 번호가 큰 양동이로 흘러간다는 조건이 있기 때문에 dp로 풀 수 있는 것 같다. ※ bfs로도 풀 수 있지만 bfs로 풀면 + 위상정렬을 같이 사용해야 해서 문제 난이도가 골드 1 ~ 2 수준으로 올라간다고 한다. ★ 풀이 1. 물의 양을 기록해놓을 dp 테이블을 만들고 1번 양동이를 100으로 초기화 해 놓은다. 2. 물은 무조건 작은 양동이에서 큰 양동이로 흘러가니가 가장 바깥 for문을 1번부터 n+1까지 해놓은다. 3. ..