본문 바로가기

분류 전체보기739

[백준 1697] 숨바꼭질 [Python] 풀이 수빈이가 동생한테 가는 방법은 현 위치(N)에 대해 3개의 방법(N + 1, N - 1, 2N)이 있다. 항상 N이 K에 가까워지는 방법이 정답이라는 보장이 없기 때문에 모든 경우에 대해 탐색을 해봐야 한다. Queue에 수빈이의 범위 내의 새로운 위치를 담아주고, 다시 꺼낼 때 이동 횟수를 기록한다. 단, 이미 방문한 위치를 재 방문할 때는 이동횟수가 같거나 크기 때문에 최소 이동횟수 기록을 보장하기 위해 방문하지 않은 경우에만 Queue에 담아두었다. Queue의 변화에 대해 궁금하다면 아래를 참고하자. 처음에 주어진 N(5)에 대한 3가지 이동 방법을 모두 기록하며, Queue에서 새로운 위치(nx)를 꺼낼때마다 이에 대한 이동 방법 또한 기록한다. 빨간색 대각선은 동일한 이동시간을 가진 위치.. 2022. 6. 4.
[백준 1012] 유기농 배추 [Python] 풀이 배추흰지렁이는 인접한 배추(기준이 되는 배추로부터 상하좌우에 위치한 배추)로 퍼져나갈 수 있다. 따라서 인접한 배추들을 전부 탐색하고, visited에 탐색한 배추를 기록하고자 한다. 결국 인접한 배추들의 덩어리인 연결 요소(Connected Component)의 개수를 구하는 문제이다. 배추가 위치한 장소만을 탐색하기 위해 배추의 위치를 입력받을 때 배추의 위치를 location에 기록한 후, DFS의 시행횟수를 세어 풀이했다. 소스코드 소스코드 보기 출처 및 참고자료 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2022. 6. 4.
[백준 11050] 이항 계수 1 [C] 풀이 C(N, K)에 대해 N의 범위는 1 ~ 10, K의 범위는 0 ~ N이므로 단순 계산으로 풀이할 수 있다. C(N, K) = N! / (K! * (N - K)! N! = N * (N - 1) * (N - 2) * ... * 1 (N - K) ! = (N - K) * (N - K - 1) * (N - K - 2 ) * ... * 1 이때, N의 sub factorial과 K! 을 구해서 나누어주면 곱셈 횟수를 줄일 수 있다. ex) N = 5, K = 2 5 4 3 2 1 2 1 3 2 1 소스코드 소스코드 보기 출처 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 2022. 4. 3.
[백준 1002] 터렛 [C] 풀이 두 좌표를 기준으로 반지름만큼의 원이 형성될 때 원의 둘레가 겹치는 좌표의 개수를 구하면 된다. 아래의 그림은 주어진 Test Case에 대한 시각화 자료이다. 만약 입력으로 주어지는 두 원이, 동일한 좌표와 반지름을 가진다면 '류재명'이 있을 수 있는 위치는 무한대이다. 두 원의 정보에 대한 입력을 struct Circle을 통해 입력받고, 두 원의 중심거리(d)와 두 원의 반지름의 차(diff_radius), 두 원의 반지름의 합(sum_radius)을 구해서 다음과 같은 비교를 통해 문제를 해결할 수 있다. 입력받은 두 원의 정보가 동일하다면 류재명이 있을 수 있는 위치는 무한대이다. d == sum_radius 이거나, d == diff_radius(아래 그림 참고)이면 한 접점에서만 만난다.. 2022. 4. 3.
[백준 2352] 반도체 설계 [C] 풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"와 푸는 방식이 동일한 문제이다. 소스코드 #include int dp[1000001] = {1000001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", back + 1); } 출처 및 참고자료 2.. 2021. 9. 5.
[백준 10800] 컬러볼 [C] 풀이 i번째 공이 잡을 수 있는 크기는 i번째 공보다 크기가 작고, 색상이 다른 공들의 합이기 때문에, 입력받은 공들을 공의 크기, 색별로 정렬을 해주었다. 출력순서는 입력순서와 동일해야 하므로, 정렬된 정보들에 대해 index별로 담아 줄 수 있는 배열들을 사용했다. for (int i = 0; i < N; i++){ scanf("%d %d", &b[i].color, &b[i].size); b[i].idx = i; } qsort(b, N, sizeof(Ball), compare); int sum_all = 0; for (int i = 0; i < N; i++){ int s = b[i].size, c = b[i].color, idx = b[i].idx; sum_all += s; same_color[c] .. 2021. 9. 5.

티스토리툴바