본문 바로가기

Problem Solving7

백준 1443 망가진 계산기 출처: https://www.acmicpc.net/problem/1443 단순하게 중복 없이 모든 경우를 계산하면 얼마일까? 수 n이 연산에 사용된 횟수를 a_n 이라 할 때, (n=2, 3, ..., 9) 중복조합의 최댓값은 p가 30일 때이므로, a_2 + a_3 + ... + a_9 = 30 8H30을 계산하면 약 1029만이 나온다. 즉, O(n) 알고리즘으로 시간복잡도를 맞출 수 있다는 뜻이다. 아래는 재귀함수를 이용해서 해결한 C++ 코드이다. 이 때, 중복되는 경우를 없애려면 재귀를 진행할 때 점점 곱하는 숫자가 커지도록 for문을 작성해야 한다. #include #include #include using namespace std; int m = 0; int idx=1; // it는 사용된 .. 2021. 2. 10.
백준 15971 두 로봇 출처: https://www.acmicpc.net/problem/15971 만나기 위해 움직여야하는 최단거리지만, 결국 통로 하나를 사이에 두고 이어진 방에서 만나는 것. 그래서 두 로봇 사이의 거리의 합에서 제일 긴 통로의 길이를 빼준 게 답이 된다. spot(정점), tot(거쳐온 거리의 합), ma(지금까지 제일 긴 통로 길이)로 구조체 만들어서 bfs 돌렸다. #include #include #include #include typedef struct a { int spot; int tot; int ma; }type; typedef struct b { int con; int len; }one; using namespace std; vector V[100005]; queue Q; int visit[1.. 2019. 2. 24.
백준 14867 물통 출처: https://www.acmicpc.net/problem/14867 A 물통과 B 물통에 든 물의 양에 대한 2차원 배열을 만들어서 visit check하며 bfs로 풀면 되지만 그럼 10만x10만이 된다. 그런데 점화식을 써보면, 두 물통에 담긴 물의 양 중 하나는 반드시 0이나 full이라는 사실을 알 수 있다. (a,b) -> (full,b) (a,full) (0,b) (a,0) / (a+b,0) or (full,나머지) / (0,a+b) or (나머지, full) 그래서 2차원 배열의 테두리만 필요하므로 공간복잡도는 문제없다. #include #include #include using namespace std; typedef struct a { int p; int q; int ct; } t.. 2019. 2. 11.
백준 13302 리조트 출처: https://www.acmicpc.net/problem/13302 이 문제는 dp배열을 방학 날과 쿠폰 개수에 대해 잡아서 풀었다. dp[n번째 날][현재 보유한 쿠폰 수 k]=min(dp[n-1][k]+10000원, dp[n-2][k-1]+25000원, dp[n-3][k-2]+37000원, dp[n-1][k-3]) dp[n-1][k-3]은 쿠폰 3개 써서 가는 경우를 말한다. 여기다가 예외 처리 해주면 된다. 그런데 배열을 너무 작게 잡아서 틀렸습니다가 많이 떴다. 쿠폰 index를 50은 잡아야 된다!! #include #include using namespace std; int n,m,k,ct=1; int dp[105][50]; bool vac[105]; int main() { cin >>.. 2019. 1. 30.
백준 10160 암호 출처: https://www.acmicpc.net/problem/10160 dp 점화식은 dp[i]=k*dp[i-1]-dp[i-5]*(long long)2+dp[i-7] dp[i-5]*2만 빼주면 안된다. 왜냐면 ABABCB_의 _에 C가 들어가는 경우도 빼주는 건데, dp[i-5]에는 ABABCB로 끝나는 문자열이 애초에 있을 수가 없다!! (안전한 암호의 개수만 저장하는 거니까) 근데 내가 문제였던 건 이게 아니었고... %1000000009를 해주므로 dp[i]가 음수가 될 수 있다. 출력은 무조건 양수므로 2018. 11. 10.
백준 9466 텀 프로젝트 출처: https://www.acmicpc.net/problem/9466 check 배열에 cycle 이뤘는지 못 이뤘는지 기록해서, check 배열에 값이 있으면 더 조사 안하고 return 함 시간초과 많이 났는데 잘 고치고 디버깅했다 반례 이거 한 번 넣어보세요 1 10 2 3 4 5 6 1 3 7 8 9 출력 4 나와야 됩니다 #include #include int T; using namespace std; int stu[100002]; int check[100002]; void makeNo(int goal,int cur) // cycle 못 이루는 거 기록 { if(check[cur]> n; for(int i=1;i 2018. 11. 10.

티스토리툴바