13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 그리디 문제만 보면 지능이 낮아지는 병이 있어서 힘들게 풀었다 그리디인건 빠르게 눈치챘는데, 어떻게 풀어야 할지 모르겠어서 질문 게시판의 반례를 쳐다보다 아이디어를 얻었다. 마감일이 N일 남은 문제는 N일 전에만 해결하면 된다. 마감일이 4일 남은 문제는 1일 차에 하든, 2일 차에 하든, 3일 차에 하든, 4일 차에 하든 상관없단 거다. '1일 차부터 N일차까지 현재 과제를 집어넣을 수 있는 날이 있는가?'를 따져보고 넣을 수 있다면 답에 점수를 더하자 작년에 푼 이 문제와 상당히 유사하다. 10775번:..
전체 글
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 머리 아파서 좀 대충 풀었다 왜인지는 모르겠지만 게리맨더링이 생각나는 문제였다. 전선 개수가 최대 99개여서 하나하나 다 끊어보는 방법이 가장 먼저 떠올랐다. 1. 부모 배열과 부모를 찾는 함수 작성(분리집합) 2. 매 케이스마다 두 집합의 크기를 구해 차가 답보다 작은지 확인하자. 3. 전선 배열을 돌면서, 해당 전선을 제외하고 모든 전선을 확인해 집합을 둘로 나눈다. 4. 부모 배열을 초기화한다. 이렇게 작성했는데, 통과하고 다른 사람 풀이를 보니 dfs 한 번만으로 해결했더라... 전선을 모두 확인해 트..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1시간 고민하고도 모르겠어서 질문 게시판에 있는 힌트를 봤지만, 문제를 애초에 잘못이해해서 힌트도 이해를 못 한 거였다;; 이 지문을 잘못이해해서, 내 양쪽 집이 둘 다 털리면 경보가 울리는 것으로 생각했었다. 그래서 첫 번째 집과 마지막 집에 포커스를 둘게 아니라, 첫 번째 집을 터느냐 마느냐만 생각하면 된다는 힌트도 이해를 못 했었다. 지문을 제대로 풀어보면 그냥 연속으로 집을 털지 말란 거다. (이 쉬운걸 왜 못 알아먹었을까) 2차원 배열로 DP 배열을 만들었고, DP[i][0]은 0번째 집을 털지 않았..