from palette import colorful_colors

접근방법1. 조합짜기먼저 주사위 중 A가 굴릴 주사위를 정할 조합을 짠다. 그러면 B가 굴릴 주사위도 자동으로 정해진다.A가 선택한 주사위는 aSelected가 1이고, B가 선택한 주사위는 aSelected가 0이다.  → 재귀 이용, makePath 함수 2. 해당 조합마다 굴리는 경우 구하기A가 굴리는 주사위의 합, B가 굴리는 주사위 합만 알면 되므로, (6^N) 이 아닌 (6^N/2) 를 두 번 구해주면 된다.굴리는 주사위의 합들을 각각의 DAT에 저장하고, 나중에 비교를 위해 합이 나오는 경우의 수를 aCase, bCase에 저장한다. →   재귀 이용, roll함수 3. 해당 조합에서 A가 이기는 경우의 수 구하기 비교시 시간복잡도를 줄이기 위해 aCase, bCase를 오름차순 정렬, 중복..

https://softeer.ai/practice/6252 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai언어: C++, 시간: 36ms 접근방법N이 크기 때문에 시간 최적화가 필요하다. 난 이진탐색의 업그레이드 버전인 Parametric search(매개변수 탐색)을 이용했다. 1. 문제에서 가능한 정답의 범위(최선의 최소 컴퓨팅 성능):  성능이 가장 낮은 컴퓨터 ~ 성능이 가장 높은 컴퓨터 + B의 루트 값 2. 최선의 최소 컴퓨팅 성능이 num일 때 예산 안에서 업그레이드가 가능한지 판별하는 함수 isPossible을 만들어준다!이후 가능한 정답 범위에서 이진탐색을 한다! → isPossible이 true면 start = mid + 1, false면 end = mid -1로 ..

https://www.acmicpc.net/problem/1149언어: C++, 시간: 0ms 접근방법대표적인 dp를 이용하는 문제. 먼저 입력을 행이 N이고 열이 3인 맵에 담고 난 후, 0행부터 N-1행까지 dp로 최솟값의 합을 저장한다: i 번째 행의 R칸에는 i-1번째의 G칸과 B칸 중 min을 저장한다.i 번째 행의 G칸에는 i-1번째의 R칸과 B칸 중 min을 저장한다.i 번째 행의 R칸에는 i-1번째의 R칸과 G칸 중 min을 저장한다....이런식으로 저장하게 되면, i번째 행의 각 열에는 i번째 집에 해당 색깔로 색칠했을때 + 그 이전 행들에 색칠하는 총 최소 비용이 저장된다.dp를 다 구하고 난 후, 정답은 N-1 행의 각 열에 담긴 숫자 중 최솟값이다. 1000 x 1000은 int 범..

https://www.acmicpc.net/problem/1715언어: C++, 시간: 36ms 접근방법정렬을 계속 반복하는 그리디 문제!가장 작은 숫자가 top에 오는 pq를 만들고 난 후,숫자들 중 가장 작은 숫자와 그 다음 숫자를 더하고, 이걸 정답 변수에 더해주고 난 후 다시 pq에 넣는다. ....→  이걸 pq 크기가 1이 될 때까지 반복하기 고려사항이 문제는 모두 int로 풀이해도 된다.문제에서 N은 10만, 카드묶음의 최대 숫자는 1000인데,정답 변수에는 1000x10만 + 2000x5만 + 4000x2만5천 + 8000x만2500, ... 이런식으로 1억이 계속 더해진다.이 때 log100000 = 16.609... 이므로, 1억이 16.609... 번 더해지는 셈이다.약 16.6억  ..