전공
-
백준 2885(초콜릿 식사)전공/알고리즘 2020. 10. 4. 23:15
www.acmicpc.net/problem/2885 2885번: 초콜릿 식사 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ... www.acmicpc.net 2^n개를 무조건 절반씩 쪼갤 수 있을때를 묻는 문제 이진수를 생각하면 된다. 구현도 쉽고 아이디어도 쉬운 문제 아 주의해야 할 점이 아래 코드에서 K==num이랑 K>num일때랑 따로 구분해서 설정해주어야한다. #include using namespace std; #define MAX 20 int main() { int K; cin >> K; int num = 1, min_n=-1, h..
-
백준 1309(동물원)전공/알고리즘 2020. 10. 4. 22:22
www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 500문제 달성 위해서 랜덤문제를 푸는 첫 문제. 그냥 점화식 찾는 문제이다. 점화식을 잘 찾아보자 근데 생각보다 점화식이 너무 어려웠다. dp[N] = dp[N-1]*2 + dp[N-2] #include using namespace std; #define MAX 100005 int dp[MAX]; int solve(int idx) { if (dp[idx]) return dp[idx]; int ret=0; ret = (solve(idx-1)*2 + solve(idx-2)) % 9901; return dp[idx] = ret; } int main..
-
브루트포스 168p clocksync전공/종만북 2020. 10. 3. 16:45
algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 �� algospot.com 먼저 규칙을 찾았었다. 어떤 스위치를 누르면 어떻게 되는지 좀 알아보다가 스위치는 10개 각각 4번씩 누르면 모든 경우의 수를 알 수 있는 문제였다. 그래서 계산을 해보니깐 시간적 여유가 있어서 그냥 브루트포스로 풀었다. 4^10 의 시간복잡도 사실 이것보다 더 오래걸릴것이다. 재귀로 구성했고, 각 재귀함수 호출마다 반복문도 들..
-
백준 10653(마라톤 2)전공/알고리즘 2020. 10. 2. 16:25
www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 문제를 보자마자 재귀의 점화식이 떠오르긴 했다. 근데 이게 dp인지는 알기가 힘들었다. dp가 뭔지 제대로 모르고 있어서 그런가 그래도 점화식을 바탕으로 dp라고 생각하고 풀었다. 처음에는 최대 K개를 계속해서 패스할 수 있다는 건줄 알고 그렇게 풀었으나 틀렸습니다.를 맞은 후에 알았다. 재귀형식으로 돌아가는 구조와, 점화식 이 두개만 알면 구현도 쉬운 dp문제이다. dp[N][K]는 N체크포인트에서 K개의 건너 뜀을 행하였을때의 최소 값을 저장한..
-
백준 1939(중량제한)전공/알고리즘 2020. 9. 30. 13:59
www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net dfs와 bfs의 차이점과 특징을 상기시켜준 문제. 처음에는 그냥 dfs로 풀었다. 그러자 TLE 최악의 경우에 거의 N*M의 시간복잡도를 가지므로, 10^9 시간초과 발생가능성이 존재한다. 따라서 시간을 더 줄일 방법을 찾아야 했다. 단순 탐색으로 풀게된다면 dfs나 bfs나 똑같이 된다. 따라서 다른 방법이 필요했다. 이진탐색을 이용해서 중량을 결정하고 탐색 ..
-
백준 5829(Luxury River Cruise)전공/알고리즘 2020. 9. 24. 00:49
www.acmicpc.net/problem/5829 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 3 -> 2(시작) -> 3 -> 4 -> 3(시작) -> 4 -> 1 -> 4 -> 1 -> 2 -> 1(시작) 어떤 점에서 시작을 한다고 하고, 그 점에서 이미 시작을 하였다면 주기반복이다. 왜냐면 어떤 점에서 M의 이동을 하여서 목적지로 이동을 한다고 하면 M의 순서는 변하지 않고, 그래프도 그대로 있으니깐 당연하다. 따라서 주기를 찾으려면 일단 모든 시작점에서 M번의 간선을 지났을 때 목적지를 구하고, ..
-
브루트포스 159p 게임판 덮기전공/종만북 2020. 9. 18. 15:19
algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 �� algospot.com 역시 완전탐색을 위한 문제. 중복을 피하기 위한 방법이 제일 중요한 문제였다. 가장 왼쪽 위부터 채워나갔다. #include using namespace std; #define MAX 25 int T, H, W; bool game[MAX][MAX]; int solve(int num) { if (num == 0) return 1; int ret = 0; int ..
-
브루트포스 155p 소풍전공/종만북 2020. 9. 18. 15:16
algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 친구끼리만 짝이 되게끔 만들어야 한다. 친구끼리만 짝이 되는 경우의 수는? 모든 경우를 다 따진 후에 친구끼리만 짝 되었을 때 세면 된다. brute force 를 사용할 수 있는 경우는 입력이 작아서, 시간초과가 나지 않을때는 가능한 것 같다. 위 문제는 이걸 위해서 만들어진 문제기 때문에 상관없다만 조심하자 아 그리고 또 항상 주의해야 할것이 중복되게 세지 않는 것이다. 중복이 생기는 ..