반응형 확률론2 [cpp 알고리즘] 백준 22984 반짝반짝2 문제 풀이 1. 첫번째는 어떻게든 0과 1의 배열의 모든 경우의 수가 2^N만큼 있으면 이를 비교해서 문제를 풀 수 있을 거라 생각했는데 0과 1의 배열의 모든 경우의 수를 구할 때 O(2^N) 으로 시간초과가 발생한다. 이를 비교해서 문제를 푼다는 것은 불이 켜졌다는 의미인 1의 개수 + 연속되는 두 수가 00,01,10,11인 경우에 대해 추가 카운트를 더한 후에 이 때의 확률을 곱하면 된다고 생각했다. 2. 그래서 배열에 저장해서 값을 바로 이용하면 될 거라 생각했지만, 메모리가 2^N만큼 발생할 것이고, N의 최대 크기가 100000이기 때문에 메모리 초과가 발생할 것이라 생각했다. 3. 이에 dp를 사용해보자고 생각해서 dp[i][j]를 이용해 i번째 까지 전구에 대해서 끈 경우를 j=0, 켠 .. 2022. 9. 13. [cpp 알고리즘] 백준 14613 너의 티어는? c++ 문제 풀이 손으로 풀어볼 때 처음에 2000점에서 시작하여 1번 게임을 하고 나면 1950점이 될 확률 1*WinRate, 2050점이 될 확률 1*LoseRate, 2000점이 될 확률 1*DRate로 생각을 했다. 2번 게임을 하고 나면 최소 점수 1900, 최대 점수 2050 사이에서 점수를 얻게 될 것이고, 1번 게임을 하고 난 1950점이 될 확률에 이길 확률, 비길 확률, 질 확률을 곱한 만큼의 확률로 +-50점의 점수들을 얻는다. 이런 방식으로 생각해서 코드를 짜게 됐다. 현재 점수가 2000점이고, 50point단위로 20번 점수를 더하거나 뺀다면 최소 점수는 1000점, 최대 점수는 3000점이다. 그리고 매번 50점 차이다. 이를 이용하여 배열을 만들었다. 1000~1499 → [0]~.. 2022. 9. 7. 이전 1 다음 반응형