백준 (223) 썸네일형 리스트형 백준 14287 - 회사 문화 3 참고 오일러 투어에 대해 모르면 여기를 먼저 보고 오자. 풀이 회사 문화 2와는 달리 더하는 방향이 반대이다. 어떻게 처리할 수 있을까? 일단 예제의 그래프를 그려보자. 여기서 정점 3에 3의 값을 더하면 1까지 3씩 더해야 한다. 하지만 단순히 간선 방향을 거꾸로만 하면 정점이 계속 중복 계산돼서 시간 초과 판정을 받고 방문 처리를 하면 사장까지 올라갈 수 없는 경로가 생겨 제대로 된 답을 계산할 수 없다. 이렇게 생각하면 무언가 떠올릴 수 있다. 부하의 칭찬을 나중에 한꺼번에 떠안자. 무슨 말이고 하면 정점 4에 5를 더하고 정점 2에 2를 더한 상태에서 정점 2의 칭찬도를 얻으려면 다음과 같이 할 수 있다. 아래로 값을 더하지 말고 2와 4의 값만 변경한 다음 2의 오일러 투어 구간 [2, 5]의 .. [KOI] 백준 8983 - 사냥꾼 https://www.acmicpc.net/problem/8983 풀이 각 동물과 사대들의 거리를 생각해보자. 사대들과의 거리를 그래프 형태로 그리면 다음과 같은 형태가 나옴을 눈치챌 수 있다. 그래프의 형태는 유니모달 함수이며 우리는 삼분 탐색으로 닿을 수 있는 가장 짧은 사대를 찾을 수 있음을 알 수 있다. 사대의 좌표를 정렬한 후 입력받은 동물 좌표마다 삼분 탐색을 실시하여 피격당할 수 있는 동물의 마릿수를 구하면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 .. [KOI] 백준 2503 - 숫자 야구 https://www.acmicpc.net/problem/2503 체크리스트 서로 다른 숫자 세 개로 구성된 세 자릿수 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번 다른 자리에 위치하면 볼 한 번 풀이 수가 단 3자리에 1부터 9까지 이므로 3자리 숫자를 모두 검색하는 완전 탐색을 생각해볼 수 있다. 이때 "서로 다른 숫자 세 개"라는 조건에 유의하여 같은 숫자가 있으면 건너뛰도록 한다. 어떤 수 조합이 후보에 포함될 수 있으려면 N개의 질의에 대해 스트라이크와 볼 개수가 일치해야 한다. 하나라도 그렇지 않으면 모순이 발생한 것이므로 생각할 수 있는 조합이 될 수 없다. 모든 수 조합에 대해 N개의 질의를 만족하는 횟수를 구하면 정답을 받을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7.. 백준 20370 - 공정한 게임 https://www.acmicpc.net/problem/20370 발상과 사전 작업 문제의 상황과는 반대로 BOT_10에게 이득인 값들을 먼저 배정한다. 그다음부터 BOT_6584가 BOT_10이 가진 값을 일부 강탈하면서 요구하는 답을 최대화시킬 것이다. 따라서 BOT_10에게 큰 값을 주도록 B의 내림차순으로 주어진 수열을 정렬하도록 한다. A는 정렬 기준을 신경 쓰지 않아도 된다. 무엇을 강탈할까? BOT_10이 가진 값을 강탈하기로 했는데 무엇을 강탈할지 잘 모르겠다. 문제를 다시 보면 [(자신이 고른 캐릭터들의 숙련도 합 - 상대방이 고른 캐릭터들의 숙련도 합)]을 최대화해야 하므로 BOT_6584의 기준으로 BOT_6584의 숙련도 합 - BOT_10의 숙련도 합이 된다. 우리는 다음과 같은.. [KOI] 백준 2507 - 공주 구하기 https://www.acmicpc.net/problem/2507 발상 단순히 가는 경우면 어렵지 않게 계산할 수 있겠는데 구출하고 돌아와야 한다. 다음과 같은 생각을 해볼 수 있다. 갔다가 돌아오는 게 아니라 그냥 2명의 사람이 밟는 발판을 겹치지 않게 이동하기 이렇게 두면 테이블이 dp[501][501]인 dp 테이블을 구상할 수 있다. 위처럼 테이블을 두면 다음과 같은 점화식을 생각해볼 수 있다. f(i, j) := 공주를 구하기 위해 i번째 돌을 밟았고 도망치기 위해 j번째 돌을 밟는 경우의 수(거꾸로) 각각 i와 j에 대해 갈 수 있는 발판을 탐색하면서 경우의 수를 더하는 탑 다운 dp를 고려할 수 있다. 유의 사항 다만 이렇게 동적 계획법을 수행하면 주의해야 할 사항이 있다. 1. j는 목적지.. 이전 1 ··· 7 8 9 10 11 12 13 ··· 45 다음
