D36CHOI

문제 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 분류 다이나믹 프로그래밍 아이디어 날짜를 index로 삼아 (1일째 = dp[1]...) 해당 일까지 얻을 수 있는 금액의 최대 이윤을 저장한다. bottom-up 방식으로, 최대 이윤을 구할 수 있는 N일부터 dp[i] 를 계산한다. 점화식은 dp[i] = max(dp[i]+dp[time[i]+i] , max_pay) 다. max_pay 는 해당일까지 계산한 최대이윤 값이다. 만약 N=7 기준으로, 7일차에 일할 경우 받는 pay = 50, 걸리는 시간 = 1이면 dp[7] = 50 이다. max_pay 또한 0에서 50 이 된다. 6일차에..

www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 테마 구현, 시뮬레이션 예상 소요시간 3~40분 아이디어 1. 주사위 배열 3*4 를 만든다. [1,1] 이 하늘은 보는 면. [3,1] 이 땅을 보는 면이다. 0x0 xxx 0x0 0x0 2. 방향을 1: 동 / 2: 서 / 3: 북 / 4: 남으로 정해 dx,dy 를 만든다. (이동) 3. 다음좌표가 (즉 굴린 후 지도 좌표) 유효하다면 다음..

app.codility.com/programmers/lessons/4-counting_elements/ 4. Counting Elements lesson - Learn to Code - Codility Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum. app.codility.com Lesson 4 Counting Elements 의 2번째 문제다. 주제는 카운팅인 것 같다. 코딜리티의 특징은, 테스트 케이스는 적게 내주고 실제 채점 케이스에서 좌절감을 느끼게 해주는 것 같다. 그래서 더 큰 도움이 ..

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 분류 DP(다이나믹 프로그래밍) C+ 코드 링크 choichumji.tistory.com/42 [C++][알고리즘] 프로그래머스:: 정수 삼각형 https://programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업 choichumji.tistory.com 삼각형의 위 꼭짓점으로부터 아래의 왼쪽과 오른쪽으로 ..

내가 생각한 분류 DFS 아이디어 1. 장애물을 놓을 수 있는 공간을 리스트로 저장해놓는다. 2. combination 을 활용해, 장애물을 놓을 수 있는 위치의 조합별로 확인한다. 3. (2) 에서 정한 장애물의 위치대로 전체 지도에 장애물을 배치한다. 4. check 함수를 통해 각 경우별로 "선생님"에게 잡히는 "학생"이 없는지를 확인한다. 5. 선생님의 위치마다 동서남북 4방향으로 "T"를 채워넣는다. (장애물이 없는경우) 6. 다 채웠으면 (DFS가 끝나면) 각 학생의 위치의 board 가 "T"인지 "S" 인지를 확인해 "S"가 아닌 경우 1명이라도 선생님에게 잡힌 경우니 이 장애물 배치는 False 다. 7. 모든 장애물 배치에 대해 "모든 학생이 감시를 피하는 경우" 가 없다면 "NO"를 ..

분류 DFS/BFS 백트래킹 브루트포스 완전 탐색 등등... 풀이자에 따라 갈리는 듯 나의 아이디어 한줄정리 모든 경우의 수를 DFS를 통해 완전 탐색함. 모든 수를 탐색한 경우의 결과 값을 최대 최소 값과 비교한다. 코드 각 연산자의 사용 가능 갯수와 연산자 기호를 매핑한 뒤 인덱스에 따른 연산을 getDeli(i, val, next) 를 통해 진행한다. C++ 14 방식을 따르는 음수 // 양수 연산에 대해서는 따로 처리해보았다. // 로 단순하게 놓으면 테스트 3번에서 막히는 듯 하다. 사용한 count를 1- 해주고 DFS 연산을 한뒤 다시 돌아올 땐 다시 1+ 해주어야 한다. 가능한 값의 범위가 -10억 ~ 10억 이므로 초기 값은 최소값 1e9+1, 최대값 -1e9-1로 설정했다.

분류 그래프 이론, BFS(너비우선탐색) 링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치�� www.acmicpc.net 전형적인 2차원 배열에서의 확장 문제. 번호가 서로다른 바이러스들이 번호순, 시간순으로 영역을 넓힌다. 상->하->좌->우 순으로 번진다고 한다. 근데 확산방향의 순서는 큰 의미는 없는듯. 서로다른 바이러스간 간섭이 방향에 의해 달라지진 않기 때문에. 중요 포인트 시간 S가 "끝났을 때" X,Y 위치의 바이러스 값을 ..