bitmask3 BOJ1014 컨닝 1014번 컨닝 N*M크기의 직사각형 교실에서 컨닝을 방지하도록 앉힐 수 있는 최대 학생 수를 구한다. 현재 위치를 기준으로 동일 행의 좌우(←→), 윗 행 좌우 대각선(↖↗) 위치의 답지를 베낄 수 있다. 비트마스킹 + DP 학생이 앉은 상태, 앉을 수 없는 자리 등을 bit로 표현하고 i행에서 k의 상태로 앉을 수 있는 학생 수의 최댓값을 i-1행을 고려해 구한다. * 3줄 요약 cnt[ k ] 행의 상태가 k일 때 해당 행에 앉는 학생의 수 (= k를 이진수로 나타낼 때 1의 개수) dp[ i ][ k ] i행에 k의 상태로 앉을 때의 최대 학생 수 dp[ i ][ k ] = dp[ i-1 ][ up ] + cnt[ k ] (up은 i행의 상태가 k일 때 i-1의 상태로 가능한 것 중 dp값이 가장.. 2021. 5. 19. BOJ1086 박성원 1086 박성원 길이 50 이하의 자연수가 N(≤15)개 주어질 때 주어진 모든 자연수를 한 번씩 사용하여 이어 붙여 만든 자연수가 100이하의 자연수 K로 나누어 떨어질 확률을 구한다. example. (A) N=3 K=27 { 104, 4, 90 } 104490 104904 410490 490104 901044 904104 여섯 개 중 세 개만 나누어 떨어지므로 1/2 출력 (B) N=3 K=13 { 12, 2, 2 } 1222 1222 2122 2212 2122 2212 여섯 개 중 두 개만 나누어 떨어지므로 1/3 출력 * s[0]="12", s[1]="2", s[2]="2"일 때, s[0]+s[1]+s[2]="1222"와 s[0]+s[2]+s[1]="1222"를 모두 세야 한다. (순열 방식이 .. 2021. 4. 21. 2019 카카오 개발자 겨울 인턴십 문제 ① 2019 카카오 개발자 겨울 인턴십 #1 크레인 인형뽑기 게임 스택 문제. 벡터로 구현했다. 더보기 #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; vector v;// as Stack int N = board.size(); for (int m : moves) { // Find position int idx = 0; while (idx < N && !board[idx][m-1]) idx++; // Pick Up & Get Answer if (idx < N) { int tar = board[idx][m-1]; board[idx][m-1] = 0; if (!v.empty() && t.. 2021. 4. 16. 이전 1 다음
