반응형 수학4 [cpp 알고리즘] 백준 1629 곱셈 [백준] 1629 곱셈 cpp 풀이 수학, 분할 정복을 이용한 거듭제곱 https://www.acmicpc.net/problem/1629 문제 요약 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어졌을 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다. 풀이 정리 - 분할 정복을 활용하여 지수를 나누어 주면 된다. (1) 지수가 0인 경우 -> X^0 = 1 이므로 1을 리턴해준다. (2) 지수가 짝수인 경우 -> X를 X/2로 나누어서, 계산한 두 값을 곱해준다. (3) 지수가 홀수인 경우 -> X를 X/2로 나누고, 계산한 두 값과 밑을 한 번 더 곱해준다. - 예제에 나왔던 A=10, B=11로 예를 들어 보면, 1. 가장 나이브하게 먼저 생각나는 방법은 for문을 이용하여 .. 2023. 11. 10. [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. [cpp 알고리즘] 백준 2839 설탕배달 c++ 1. 문제 2. 풀이 3. 코드 #include #include using namespace std; int N; int dp[1001][5]; int ans =0; int main(){ // input cin >> N; // 마지막 자릿수 확인 if(N%10==0 || N%10==5){ ans = N/5; } else if(N%10==1 || N%10==6){ ans = 2+(N-3*2)/5; } else if(N%10==2 || N%10==7){ ans = 4+(N-3*4)/5; } else if(N%10==3 || N%10==8){ ans = 1+(N-3*1)/5; } else if(N%10==4 || N%10==9){ ans = 3+(N-3*3)/5; } // except if(N==4 || N=.. 2022. 7. 13. 이전 1 다음 반응형
