문제 1463 - 1로 만들기 접근 DP를 이용하는 문제이다. 바텀업 방식으로 풀었다. N에서 1로 만드는 방법이지만, 1부터 N까지 타고 올라갔다. dp[1]은 0으로 시작하고, n까지 올라가며 dp[i] = dp[i-1] + 1을 해준다. 이러면 1을 빼는 연산에 대해서 처리해준 것이다. 그리고 i가 3으로 나눠지거나 2로 나...

문제 7785 - 회사에 있는 사람 접근 Key를 이름, value를 출근/퇴근 flag로 구성하여 딕셔너리를 만들면 된다. 입력이 끝난 후 딕셔너리를 순회하며 현재 value가 출근인 사람들만 추린 후, 정렬하여 출력한다. 코드 파이썬 코드 import sys input = sys.stdin.readline if __...

문제 4796 - 캠핑 접근 그리디 문제이다. 연속하는 P일 중에 L일은 캠핑을 할 수 있다. 즉, P일 중에 캠핑을 한 날이 L일을 넘지않으면 무조건 캠핑을 하는게 이득이다. 이에 따라 전체 휴가인 V일을 P일로 나눈 몫을 a라고 할 때, a*L일은 확정적으로 캠핑을 할 수 있는 날이다. 문제에서 주어진 예시인 5, 8, 20으로...

문제 2309 - 일곱 난쟁이 접근 완전 탐색 문제이다. 문제의 조건을 만족하는 경우를 직접 구해서 출력해야 한다. 보통 이런 문제를 풀 때 정답 배열을 만들고 넣었다 뺏다 하는 식으로 풀었었는데, 오늘은 조금 다르게 풀어봤다. 7명의 키를 더했을 때 문제의 조건인 키의 합이 100이면 True를 반환하고 아닌 경우 False를 반...

문제 2805 - 나무 자르기 접근 문제 자체는 간단하다. 나무의 높이를 가지고 이분탐색을 진행하면 된다. 높이 보다 큰 값에 대해 어짜피 연산을 진행해야 하므로(높이만큼 잘라야한다) 정렬하는데 걸리는 시간이 더 걸릴 것 같아서 따로 정렬은 진행하지 않았다. 문제를 정의하기가 조금 까다로웠다. 기존 이분 탐색 문제는 뭔가 딱 비례관...

문제 5373 - 큐빙 접근 너무 끔찍한 구현문제였다… 문제보고 하기싫어서 밍기적밍기적거리다가 겨우 풀었다.. 한 면을 회전시키면 해당 면은 Rotation 해준다. 해당 면과 인접한 네개의 면은 인접한 부분들만 다른 면들과 교체해준다. 나머지 한 면은 변화가 없다. 예를 들어 윗면을 돌린다고하면, 윗면은 테두리가 전체적으로 회전한다....

문제 17144 - 미세먼지 안녕 접근 단순 구현 문제이다. 크게 나누면 미세먼지가 확산되는 부분과 공기청정기가 작동하여 공기가 순환되는 부분으로 나뉜다. 미세먼지의 확산 같은 경우 전체 칸에서 미세먼지가 동시에 확산된다고 한다. 이 부분은 한칸씩 작업을 하게되면 처리할 수 없다. 나는 배열을 두 개만들어서 원래 미세먼지 배열을 확인하...

문제 15685 - 드래곤 커브 접근 문제를 부분 문제로 쪼개서 생각하면 쉬워진다. 우선 드래곤 커브를 그릴 줄 알아야 한다. 현재 주어진 좌표 중 마지막 좌표를 기준으로 회전한다. 그럼 한 세대를 거칠 때마다 마지막 좌표는 어떻게 바뀔까? 마지막 좌표를 기준으로 회전하니, 회전이 끝나면 마지막좌표는 항상 최초좌표가 회전한 좌표가 될 것...

문제 2618 - 경찰차 접근 너무 어려웠다.. 사건이 N개 발생했을 때 이동할 수 있는 경우의 수는 2^N개가 된다. 일단 DP인건 확실한데,, 어떻게 구성할지 감도 안잡힌다. 결국 종이에 N을 작게해서 경우의 수들을 그려봤다. 이 때 좌표를 생각하지말고 그냥 사건의 idx로 생각하면 좀더 쉬워진다. 좌표는 나중에 다시 생각하자.. ...

문제 17143 - 낚시왕 접근 뭐랄까 굉장히.. 성가신 구현 문제였다. 일단 상어의 상태를 나타내야하는 변수가 너무 많다.. 클래스나 연습해볼겸 클래스로 구현했다. 주어지는 상어의 상태 외에 상어마다 고유 번호를 부여해줬다.(idx) idx는 나중에 상어끼리 잡아먹을 때 활용할 생각으로 만들었다. 또한 survive 라는 속성을 주어 ...