📊알고리즘/BOJ101 BOJ 1106 - 호텔 https://www.acmicpc.net/problem/1106그리디로 풀 수 없는 이유그리디로 처음에 시도를 했다. 그러나 이 문제는 그리도로 절때 풀 수 없다.원 당 모집 인원 수가 가장 많은 것을 고른다고 가정해보자.1번 예시에서 반례가 발생한다.```12 23 51 1```3원 - 2명은 원 당 1.66666667명을 모집한다.따라서, 그리디에선 3원을 3번 선택하여 9가 정답이지만예시의 예상 출력 값은 8이다.따라서, 이 문제는 그리디 대신 `dp`를 이용하는 것이 옳바르다.DP 풀이DP[i]를 i명 모집 시의 최소 비용으로 두자. 호텔 A가 3원 당 5명이고 호텔 B가 1원 당 1명이라고 하자. DP[i]는 DP[i-3] + 5 일 수도 있고, DP[i-1] + 1 일 수도 있다. 이전 인원.. 2024. 10. 29. BOJ 1034 - 램프 https://www.acmicpc.net/problem/10341차 시도처음 그리디를 이용하여 0의 개수가 가장 많은 열을 스위치 작동시키는 방법을 구상했다.O(N*M)이 걸렸지만 스위치 작동 후의 0을 구하는 과정과 켜진 행을 찾는 구간 때문에 시간 초과가 발생했다.더 빠른 방법을 구상해보기로 했다.2차 시도우선 규칙이 보였다.한 행에서 0의 개수가 k보다 크면, 해당 행은 완전히 켜질 수 없다.한 행의 0의 개수와 k의 홀짝이 다르면, 해당 행은 완전히 켜질 수 없다.2번의 경우, 밑에 예시로 보자3 30101011014일 경우, 2번째 열을 홀수번 킬 때 2,3번 행이 완전히 켜지게 된다.그러나 k가 짝수이기 때문에 2,3번 행은 처음과 같은 상태가 된다.3 30101011013반면, k가 홀수가.. 2024. 10. 28. [랜덤] BOJ 1091 - 카드 섞기 https://www.acmicpc.net/problem/1091 아이디어: 10분코딩: 15분 접근법카드를 석는 방법대로 카드의 위치를 옮기는 것이 핵심인 문제이다.이는 직접 과정을 하나하나 하다보면 점화식을 구할 수 있다. 먼저 현재 카드를 before={0, 1, 2, 0, 1, 2}이고, 섞는 순서를 S={1 4 0 3 2 5}라고 가정해보자. 그리고 섞은 후의 배열을 after[]라고 하자. S를 0번부터 ~5번까지 돌면서 각 상황을 보자. before의 S[0]번째 카드는 after의 0번으로 이동해야한다.이를 식으로 표현하면 after[0] = before[S[0]] before의 S[1]번째 카드는 after의 1번으로 이동해야한다.이를 식으로 표현하면 after[1] = before[S.. 2024. 10. 25. [랜덤] BOJ 1011 - Fly me to the Alpha Centauri (C++) 문제 링크백준 1011풀이 시간아이디어: 20분코딩: 10분문제 풀이조건)처음과 끝 직전에는 무조건 속도 1로 도달해야한다.K번째 턴의 속도 V[K]는 V[K-1]-1, V[K-1], V[K-1]+1조건을 해결하기 전 먼저 어떤 규칙이 있을 것 같다고 생각했다.예를 들어 A=0, B=10이라고 가정하자.구간의 길이는 총 B-A = 10이다.눈으로 계산해보면0 -(+1)-> 1, 1 -(+2)-> 3, 3 -(+3)-> 6, 6 -(+2)-> 8, 8 -(+1)-> 9, 9 -(+1)-> 10 이다.가운데 값을 기준으로 양쪽으로 내려가는 것을 볼 수 있다.무엇보다 끝에 +1이 두번 나오는 것을 통해, 남는 거리만큼 +1을 하면 될 것 같다고 생각했다.이를 표로 남겨보자왼쪽 칼럼을 속도라고 했을 때 개수.. 2024. 10. 20. BOJ 27172 - 수 나누기 게임 https://www.acmicpc.net/problem/27172 1차 시도카드를 서로 비교하여, 나누어 떨어지는지 비교하면 된다.카드가 100000장 이기 때문에 브루트포스로 모두 비교하면 시간초과가 발생한다.따라서, 비교할 필요가 없는 카드를 선별하면 된다고 판단. 비교할 필요가 없는 카드 = 소수이므로 에라토스테네스의 체를 이용하여 소수를 선별하고, 해당 플레이어는 패스하도록 설계했다. 당연하게도 시간초과.왜냐하면 최악의 경우(소수가 없는 경우) 모든 수를 비교하기 때문에 O(N^2)이 걸린다. 접근소수를 찾고 진행하는 대신 플레이어 숫자의 배수인 카드를 가진 플레이어를 찾는 것이 훨씬 빠르게 작동한다. #include #include #include #include #include #includ.. 2024. 8. 29. BOJ 2239 - 스도쿠 https://www.acmicpc.net/problem/2239 접근법백트래킹 연습용으로 널리 퍼져있는 문제이다.스도쿠 빈칸에 알맞은 번호를 넣으면, 이 번호에 의해 다른 빈칸에 무엇이 들어가는지 결정된다.따라서, 만약 이전 선택이 잘못됐을 경우 돌아가야한다.이를 백트래킹을 이용해 구할 수 있다.보다 구체적으로 설계를 해보자. 1. 빈칸을 돌면서 해당 빈칸에 들어갈 적절한 번호를 선별한다.2. 선별된 번호를 빈칸에 넣고, 재귀적으로 다음 빈칸을 수행한다.3. 만약 빈칸을 모두 매꾸었으면 정답이므로 배열을 출력한다.4. 만약 이후의 빈칸에 적절한 숫자를 넣을 수 없는 경우, 재귀를 종료하여 이전으로 돌아가도록한다. #include #include #include #include #include #incl.. 2024. 8. 27. 이전 1 2 3 4 ··· 17 다음
