줌코딩의 코딩일기

문제 문제 링크 어떻게 접근할 것인가 이 문제는 디피로 접근할 수 있다. 같은 색을 두번 연속 선택할 수 없으므로 각 지점에서 각 색깔을 선택했을 때의 최소값을 저장할 수 있어야 한다. 이를 위한 어레이를 준비하고 전이 빨간색이었다면 현재 값의 초록색 값과 파란색의 값을 최신화시켜주도록 한다. 코드 #include <cstdio> #include <vector> using...

문제 문제 링크 어떻게 접근할 것인가 피보나치 수열을 변형시키는 문제이다. 0과 1의 개수를 담는 어레이를 만들고 0과 1에 해당하는 값을 저장하고 디피로 다음 값을 업데이트 해간다. 코드 #include <cstdio> int zero[41], one[41], n, k; int main(){ zero[0] = 1; one[1] = 1; for(int i = 2; i <= 40; i++){...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 높이에 몇개 벽이 있는지를 어떻게 기록할 것인가가 관건인 문제이다. 이분탐색으로 풀 수도 있겠지만 내가 생각해낸 방법은 이거였다. 일단 그냥 일일이 기록하면 시간 초과가 뜨게 된다. prefix sum을 이용하면 효율적으로 풀 수 있다. 만일 인풋이 5라고 하면 시작점부터 5까지 값이 모두 있다고 볼...

문제 문제 링크 어떻게 접근할 것인가 달팽이가 정상에 올라가는데 걸리는 날의 최솟값을 구하는 문제이다. 즉, 날짜의 lower_bound를 찾는 문제이다. 여기서 주의할 점은 달팽이의 위치는 하루 전날까지는 올라간 높이 빼기 내려간 높이이지만 당일은 올라간 높이만이다. 그래서 이분 탐색을 이용해서 정상에 도착하지 못하는 애들의 upper_bound를 찾아주고 이를 + 1 해준 값을 출력한다.(이것이...

문제 문제 링크 어떻게 접근할 것인가 index로 찾는다고 하면 그냥 어레이의 index값을 출력하면 된다. 하지만 이름으로 찾는다고 binary search를 위해 정렬된 어레이가 필요하다. 이를 위해서 어레이를 하나 더 준비하고 여기에는 이름과 index를 같이 넣어준 후 찾고자 하는 이름의 이전 위치를 찾기 위해 upper_bound를 진행하였다. 그 후 찾아진 값에 저장되어있는 인덱스...