정리하기 위한 블로그 정리하기 위한 블로그

문제가 넘 어려워서 다른 분의 풀이를 참고하여 이해하였다 접근 과정 트리 dp 1. dp[k][0] - k팀의 팀장이 뽑히는 경우 2. dp[k][1] - k팀의 팀원이 뽑히는 경우 팀 이름은 팀장의 번호를 따라감 d[k][0]은 본인의 매출, d[k][1]은 0으로 세팅 1. 내가 팀장으로 뽑힐 때 내 팀원이 팀장으로 뽑힐 때, 팀원으로 뽑힐 때 모두 고려해야 함 d[k][0] += min(d[child][0], d[child][1]) 2. 이 경우 역시 d[child][0], d[child][1] 중 최소값을 전부 더해주면 되지만 두 가지 케이스로 나뉨 i) d[child][0]이 최소인 팀원이 하나라도 있을 때, 땡큐인 상황 1번과 똑같이 진행 d[k][1] += min(d[child[0], d[c..

동영상 재생시간과 공익광고 재생 시간 범위가 00:00:01 이상 99:59:59 이하이므로 360000의 크기 안에서 시청자 재생시간의 시작 시각과 종료 시각을 카운트 해준다. 광고 재생시간의 left, right 포인터를 가지고 이동시키며, 위에서 카운트 해준 값을 이용해서 left, right의 가중치 k, kk 를 빼고 더하며 시청자들의 누적 재생시간의 합을 계산해준다. 이때 시청자들의 누적 재생시간의 합이 최대 360000 * 300000 으로 int 범위를 넘어갈 수 있기때문에 long long 을 고려해주는 게 중요했다. 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 ..

3*2*2*2 케이스에 대해 벡터를 만들고 값을 집어 넣는다 그 후 정렬한 뒤 각각 upper bound를 구하며 쿼리문의 결과를 구한다. 돌아돌아 구현한 느낌이 드는데 더 간단한 풀이가 있는지 찾아봐야겠다. 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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97..

java나 python은 substr이 (start,end)로 end index 전까지인데 c++ 의 substr은 (시작위치, 개수) 인걸 헷갈렸었따... 문자열은 제일 앞부터 정해진 길이만큼 잘라야 하고 문자열의 길이가 최대 1000이므로 n^2으로 충분히 가능하다. substr으로 정해진길이의 다음 substr을 검사하면서 진행해준다. 이때 신경써야할 부분은 cnt의 숫자에 따라 문자열의 길이가 달라진다는 점이다. 최대 1000이므로 적당히 if else로 처리해준다. 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 4..

상반기에 실전에서 매우 애먹었던 문제이다. 다시 풀어보니 쉽게 풀 수 있었는데 깨달은 점이 하나 있었다. (이런 구현문제는 효율을 크게 생각안하고 시도 하는게 포인트인 것 같다.) 일단 연산자가 최대 3개이고 우선순위 경우의 수가 6가지이고 우선순위에 따른 계산 시 시간복잡도는 고려하지 않아도 될정도로 적으므로 (string 최대길이가 100이므로) 마음놓고 dfs 완탐을 해도 된다. 당시에 애먹었던 이유는 원본 벡터를 복사한 temp 벡터 하나만 가지고 연산을 하려했었다.. 그래서 list를 사용해야하나 아니면 vector로 remove하며 해야하나 고민하는데 시간을 허비했다. 굳이 그럴 필요없이 연산자에 의해 계산된 결과를 담는 벡터(t,tt)를 하나 더 이용하면 된다. 연산자의 개수 + 1 = 피연..

https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 이런류의 문제는 dp로 n^2 풀이가 가능하다 다만 차의 방향상태를 나눠서 저장해준다. dp[i][j][0] = i,j에서 차가 오른쪽으로 갈 수있는 경우의 수 dp[i][j][1]= i,j에서 차가 아래로 갈 수있는 경우의 수 그 후 city_map이 0이냐 1이냐에 따라 다르게 처리를 해준다. 0인 경우 : 현위치에서 위에서 오는 경우의 수 왼쪽에서 ..