목록수학 (34)

1일1알

백준 1292번 쉽게 푸는 문제 C++

누적 합을 저장하는 벡터를 만들어서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector sum(1001, 0); int num = 1; int cnt = 0; for (int i = 1; i > left >> right; int ans = sum[right] - sum[left - 1]; ..
알고리즘 2022. 4. 21. 16:05
백준 1405번 미친 로봇 C++

백트래킹을 이용해서 마지막 이동까지 마쳤을 때 이동 경로가 단순한 로봇들이 지나온 길의 확률들만 모두 더하는 방식으로 문제를 해결하였다. 중간에 이미 방문한 곳을 가려고 하면 그곳은 탐색을 하지 않았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[4] = { 0,0,1,-1 }; int dCol[4] = { 1,-1,0,0 }; vector visited(30, vector(30, false)); vector proV(4); int ..
알고리즘 2022. 3. 17. 12:19
백준 2748번 피보나치 수 2 C++

dp[ i ] = dp[ i - 2 ] + dp[ i - 1 ] , int 범위를 넘어가기 때문에 long long으로 선언하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector dp(91, 0); dp[1] = 1; int n; cin >> n; for (int i = 2; i
알고리즘 2022. 2. 26. 11:09
백준 10253번 헨리 C++

단위분수의 분모를 정하는 것이 이 문제의 핵심인 것 같다. 분모에서 분자를 나눈 값의 나머지가 0이라면 분모 / 분자 를 다음 단위분수의 분모로 하였고, 0이 아니라면 (분모 / 분자 ) + 1 을 다음 단위분수의 분모로 정하였다. 첫번째 예제로 예를 들자면 23 / 4 = 5 ... 3 이기 때문에 다음 단위분수의 분모는 5 + 1 = 6 이고 1 / 6 과 4 / 23 을 통분하면 23 / 138 과 24 / 138 이 된다. 이렇게 구하는 것이 분자 / 분모 보다 작은 단위분수 중 가장 큰 값 이라고 생각했다. 만약 단위분수의 분모를 그냥 1씩 증가시키면서 계산을 한다면 시간초과가 날 것이다. 그리고 오버플로우도 조심해서 풀어야 한다. #include #include #include #include..
알고리즘 2022. 2. 4. 15:32
백준 2818번 숙제하기 싫을 때 C++

주사위는 마주 보는 면의 합이 7이기 때문에 세 면의 정보만 알고 있으면 어디로 구르든 다음 위에 오는 숫자의 정보를 알 수 있다. 그리고 4번 구르면 원래 상태와 같아지기 때문에 많이 가야하는 경우는 이것을 이용해 한번에 이동할 수 있다. 그리고 행*열*주사위 최고 수 = 100000*100000*6 은 int 범위를 넘어가기 때문에 주의해야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[4] = { 0,1,0,1 }; int dCol[4] =..
알고리즘 2022. 2. 1. 22:37
백준 2777번 숫자 놀이 C++

한 자리수 중 가장 큰 수인 9부터 2까지의 곱으로 나타낼 수 있는지 확인하고 가능하다면 그 개수를 출력하고, 가능하지 않다면 -1을 출력한다. 1은 따로 처리해 주었다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t, n; cin >> t; while (t--) { cin >> n; if (n == 1) { cout
알고리즘 2022. 1. 29. 15:47
이전 Prev 1 2 3 4 5 6 Next 다음