본문 바로가기
반응형

알고리즘

14495번 14495번 - 피보나치 비스무리한 수열 그냥 짰더니 시간초과가 발생하여 DP 로 접근하여 문제를 풀 수 있었다. 그리고 int 형을 초과하기 때문에 long long 타입으로 바꿔줘야 AC를 받을 수 있었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include#includeusing namespace std; long long D[117]; long long fibo(int n){ if (n = 0) { return D[n]; } if (D[n] == -1) { D[n] = 0; } D[n] += fibo(n - 1) + fibo(n - 3); return D[n];}int main(int argc.. 더보기
1009번 1009번 - 분산 처리 주어진 값 중에서 a^b 는 최대값을 넣어보면 너무 큰 값이 나오기 때문에 담기가 불가능해보였다. 어차피 나머지 연산은 겹쳐서 계산을 해도 되기 때문에 b번만큼 a를 곱하면서 나머지만을 구했다. 그리고 나머지가 0인 경우에는 10번 컴퓨터 이므로 10을 출력하도록 했다. 123456789101112131415161718192021222324252627282930313233#includeusing namespace std; int main(int argc, char** argv){ ios::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; for (int t = 1; t > a >> b; int ret = 1; for (int .. 더보기
1920번 1920번 - 수 찾기 만약 이중포문으로 돌 경우에는 시간초과가 발생하기 때문에 이분탐색을 이용해서 문제를 풀었다. 그러면 포문에서 M번 돌고, 소트된 배열을 이진 탐색하는데 logN 이기 때문에 시간안에 돌 수 있을거라고 생각했다. O(MlogN) 이 되므로 시간에 통과할 수 있게 된다. lower_bound 와 upper_bound 를 이용해서 해당하는 값을 찾고, l 과 r 이 같을 경우는 존재하지 않으므로 0을 출력하고 나머지 경우에는 존재하므로 1을 출력한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include#include#includeusing namespace std; int main(in.. 더보기
10250번 10250번 - ACM 호텔 그냥 for문의 순서만 바꿔서 출력하면 되는 문제였는데 생각보다 정답률이 낮아서 쫄았다. 어차피 엘리베이터를 타는 건 걷는거에 포함되지 않으므로, 엘리베이터 가까운 곳부터 방을 배정하면 된다. 따라서 101,201,301,....,102,202,302,..... 이런식으로 방을 배정하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include#includeusing namespace std; int h, w, n;int main(int argc, char** argv){ ios::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc;.. 더보기
2548번 2548번 - 대표 자연수 N제한이 2만이고 이중 포문으로 풀었기 때문에 시간초과가 발생하지 않을까 했는데 발생하지 않았다.. 그래서 다른 분들 코드를 보니까 엄청 간단하게, 정렬후 중간값보다 조금 작은 값으로 하는데 잘 이해가 가지 않았다. 그래서 백준 SLACK 을 통해서 물어보니 y = |x-1| + |x-3| + |x-6| 의 그래프를 x=3 일때 최소값이다는 것을 생각해보라는 갓님의 말... 한방에 이해가 갔다. 문제 푸는 속도가 굉장히 많이 차이가 났다.. 12345678910111213141516171819202122232425262728293031#include#includeusing namespace std; int n, ans, MIN = 1987654321;int num[20001];.. 더보기
15312번 15312번 - 이름 궁합 나는 큐를 사용해서 문제를 풀었다. vector 나 배열을 사용해도 되지만 크기를 줄여나가야 하기 때문에 큐가 적합할 거라고 생각했다. 로직은 큐에 처음에 글자들의 개수를 담는다. 만약 예시처럼 6 2 5 4 5 이렇게 담겼다면 6 을 꺼내고 팝시켜서 6을 없애고 2를 꺼내서 두수를 더하고 그 값을 큐에 넣는다. 그 다음에는 2를 꺼내고 팝 시켜서 2를 없애고 5를 꺼내서 두수를 더하고 그 값을 큐에 넣는다. 이런식으로 큐의 크기가 2가 될때까지 줄여준다. 그리고 마지막에 큐 값 두개를 꺼내서 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152.. 더보기
1076번 1076번 - 저항 숫자의 범위와 string 문자열을 잘 사용하면 쉽게 풀 수 있는 문제. 처음에 stoi 함수를 쓰려다가 int 범위를 벗어나는 것 같아서 , 문자 3개를 전부 입력 받고 for문에서 맨마지막 문자열부터 시작해서 숫자를 맞춰나갔다. stoi 처럼 string 을 long long 으로 바꾸는 함수는 없는가? => 찾아보니 stoll 이 존재했다.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include#include#includeusing namespace std; string om[10] = { "black","brown","red","orange","yello.. 더보기
1010번 1010번 - 다리놓기 D[n][m] = 왼쪽n개,오른쪽m개 있을 때 놓을 수 있는 다리의 경우 라는 점화식을 세워서 문제를 풀었다. 기저 조건으로는 - 왼쪽에 세울 다리가 남았는데, 오른쪽 다리가 부족한 경우 return 0 - 왼쪽에 세울 다리가 없을 때, return 1; for문을 통해서 왼쪽과 오른쪽을 연결하는데, 오른쪽으 가장 위쪽부터 아래로 내려가게끔 연결시켰다. 풀고 다른 분들을 보니 그냥 조합의 갯수를 구해서 바로 푸셨다.. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include#includeusing namespace std;int D[31][31.. 더보기
반응형

티스토리툴바