목록백준 (475)

1일1알

백준 10835번 카드게임 C++

오른쪽 카드가 왼쪽 카드보다 작은 경우와, 큰 경우 두 가지로 나누어서 문제를 해결하였다. 오른쪽 카드가 왼쪽 카드보다 작은 경우는 1. 오른쪽 카드의 점수를 얻고 오른쪽 카드를 빼는 경우 2. 왼쪽 카드를 빼는 경우 3. 양쪽 카드를 빼는 경우 이 세 가지 중 큰 값을 구했고 반대의 경우에는 1. 왼쪽 카드를 빼는 경우 2. 양쪽 카드를 빼는 경우 이 두 가지 중 큰 값을 구했다. 그리고 같은 지점을 계속 탐색할 수 있기 때문에 시간 초과나 스택 오버플로우가 발생할 수 있다. 그렇기 때문에 메모이제이션 기법을 통해 dp배열에 방문한 곳을 저장해서 바로 빠져나올 수 있게 작성하였다. #include #include #include #include #include #include #include #incl..
알고리즘 2021. 12. 22. 13:03
백준 9009번 피보나치 C++

1,000,000,000 까지 포함할 수 있는 피보나치 배열을 만들고, 큰 값부터 빼가면서 답을 구했다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; vector fib(47); fib[0] = 0; fib[1] = 1; for (int i = 2; i < 47; i++) { fib[i] = fib[..
알고리즘 2021. 12. 21. 11:15
백준 15661번 링크와 스타트 C++

백트래킹으로 문제를 해결하였다. 가능한 링크 팀의 경우의 수를 모두 구하고, 링크 팀의 팀원이 아니라면 스타트 팀에 넣고, 각각의 경우마다 두 팀의 점수의 차의 절댓값 중 가장 작은값을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; vector v(21, vector(21, 0)); vector link; int ans = 987654321; int gap() { int score_link = 0; int score_start = 0; vector..
알고리즘 2021. 12. 20. 11:53
백준 3079번 입국심사 C++

이분 탐색으로 시간을 탐색하면서 시간 내에 검사를 다 할 수 있으면 시간을 줄이고, 할 수 없으면 시간을 늘리는 방식으로 문제를 해결하였다. 주의해야할 점은 사람의 수의 최대는 10^9 이고, 걸리는 시간의 최대도 10^9 이기 때문에 최악의 경우에는 10^18이 나올 수도 있다. 그러므로 long long을 사용해야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; ll n, m; vector v(100001); bool solve(ll mid) { ll cnt ..
알고리즘 2021. 12. 19. 11:59
백준 15486 퇴사 2 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 상담을 하는데 걸리는 시간이 있기 때문에 상담을 시작한 시간이 아닌, 상담이 끝난 시간을 기준으로 점화식을 세워야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n + 1, { 0,0 }); vector dp(n + 1, 0); ..
알고리즘 2021. 12. 18. 14:37
백준 16194번 카드 구매하기 2 C++

https://kjhcocomi.tistory.com/11 백준 11052번 카드 구매하기 C++ 한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 kjhcocomi.tistory.com 이 문제와 유사한 문제이다. 금액의 최대가 아닌 최솟값을 구하면 된다. 여기서는 최솟값을 구해야 하기 때문에 초기값을 넣어주어야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; t..
알고리즘 2021. 12. 17. 12:18
이전 Prev 1 ··· 73 74 75 76 77 78 79 80 Next 다음