링크 https://www.acmicpc.net/problem/20551 난이도(solved.ac 참고) 실버4 풀이 실버4라 만만하게 봤는데 생각보다 시행착오를 많이 겪었던 문제였다. 일단 이분 탐색을 사용해야 되는 문제였는데, 거기서도 lower_bound라는 개념을 익힐 수 있는 문제였다. lower_bound란 찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수다. 이분탐색에서 살짝만 바꿔주면 된다. 물론 당연히 이분탐색의 전제와 같이 sort가 되어있어야 한다. mid를 가운데 값으로 설정하고 target보다 작으면 mid+1로 왼쪽 범위 날리고, target보다 크면 right = mid - 1로 오른쪽 범위 날리고, 같을 경우가 문제다. [-1, 1, 3, 3, 3, 4, 5, 6, 6..

링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 난이도(solved.ac 참고) 실버1 풀이 다이나믹 프로그래밍 문제다. DP 배열을 선언하고 첫 값은 input값으로 받은 street의 첫 열을 그대로 갖다 붙인다. 다음 열로 넘어갈 때 각 dp의 값은, 이전 열의 같은 행 값이 아닌 다른 행의 값들에 + 현재 위치한 인덱스의 street값을 더해준 것 중 더 작은 것을 넣어준다. 이 과정을 반복하고 가장 마지막 열..

링크 https://www.acmicpc.net/problem/2166 난이도(solved.ac 참고) 골드5 풀이 다각형의 넓이를 구하기 위해서 우리가 고등학교 시절에 수학시간에 배웠던 신발끈 공식을 사용해야 한다. 신발끈 공식이란 n각형이 있을 때에 (x1, y1), (x2, y2), .., (xn, yn)이 있다고 할 때 이 넓이는 1/2 * | (x1*y2 + x2*y3 + .. + xn-1*yn + xn*y1) - (y1*x2 + y2*x3 + .. + yn-1*xn + yn*x1) | 와 같다는 공식이다. 자세한 건 나무위키를 참조하기 바란다. 이 문제는 이 신발끈 공식을 구현하면 되는 문제였다. 전부다 구하고 마지막에 2로 나눠준 뒤 절댓값을 씌워주면 해결할 수 있는 어렵지 않은 문제였다.

링크 https://www.acmicpc.net/problem/1092 난이도(solved.ac 참고) 골드5 풀이 가장 높은 중량을 들 수 있는 크레인에 가장 무거운 박스를 배치하면 된다. 크레인에 대한 반복문이 끝나면 1회 순회한 것이므로 while문 직후에 time이라는, 우리가 답으로 출력할 변수의 값을 1씩 증가해준다. 그리고 크레인의 값이 더 클 경우에 break을 함으로써 weight에 대해 불필요하게 남은 box에 대한 반복문을 돌 필요가 없게끔 하였다(break없이 돌면 안돼서 넣은 것이기도 함).

링크 https://www.acmicpc.net/problem/2170 난이도(solved.ac 참고) 골드5 풀이 문제를 보자마자 생각했던 것은 1) 처음 input으로 받은 y - x의 값을 길이를 나타내는 변수인 leng에 초기값으로 두고, 이 y값을 target으로 설정한 다음 2) 정렬이 되어있다는 전제 하에, 이 첫번째 y와 같은 x가 나올 때까지 leng의 값에 (y의 값들 - target)을 더해주고 target을 각 y로 바꿔주는 방식으로 업데이트하자 3) 계속 target값을 업데이트하던 와중에 새로운 x값이 target보다 클 경우 선이 끊어져 있다는 뜻이므로 여기서는 leng에 (새로운 y값 - 새로운 x값)을 더해준 다음 target은 똑같이 새로운 y값으로 바꿔주자 라는 것이었다..

링크 https://www.acmicpc.net/problem/1850 난이도(solved.ac 참고) 실버2 풀이 input값 만큼의 1의 개수로 이뤄진 두 수의 최대공약수를 구하는 문제이다. 그냥 result에 '1'의 개수만큼 넣어서 구하면 메모리 초과가 뜬다. 그럴만도 한게 예제 입력 중에 500000000000000000이라는 매우 큰 수가 있기 때문. 저걸 다 구할 필요가 없다. 몇 자리 수인지만 알면 된다. 왜냐면 어차피 어떤 수든 간에 1로 바꿔준 수들이기 때문.. 일반적인 두 수의 최대 공약수를 구한 다음 그 갯수만큼 1로 바꿔주면 된다.

링크 https://www.acmicpc.net/problem/17352 난이도(solved.ac 참고) 골드5 풀이 input값을 받은 것들이 속하는 집합을 만든다. a와 b를 input으로 받았다면 각 a와 b의 루트 노드를 찾아서(find_parent 함수로) 더 작은 값이 부모 노드가 되는 방식이다. 현재 문제에서는 다리 하나만 놓으면 모든 노드가 전부 연결이 되어 있는 상태이다. 즉, n개의 섬 중 단 하나의 부모 노드만 다르다는 것이다. 그 값을 찾아서 (n-1개의 섬의 부모 노드, 나머지 하나의 섬의 부모 노드)의 값을 출력해주면 되는 문제였다. 이렇게 출력하면 되는 이유는, 부모 노드끼리 연결함으로써 최종적으로 모든 섬에 다 갈 수가 있게 되기 때문이다.

링크 https://www.acmicpc.net/problem/14502 난이도(solved.ac 참고) 골드5 풀이 1. input값으로 받은 a 리스트를 돌면서 값이 0이라면 전부 candidate라는 리스트에 인덱스 형태로 넣어주고(ex. (0, 1)), 2라면 큐에 담는다. 2. candidate 리스트에서 3개를 뽑아내는 순열 반복을 하면서 큐와 a를 각각 카피해서 새로운 변수에 지정해주고 그 순열에 해당하는 부분에 대해 a_copy 내의 해당 인덱스의 값을 1로 바꿔준다. (3개를 뽑아 벽을 세우는 것) 3. 그다음 result라는 변수에 bfs 함수의 리턴값을 부여한다. 3-1. bfs 함수에서는 a_copy 내의 값이 0일 경우 전부 2로 바꿔준 뒤 큐가 비게 되면 while문이 끝나면서 ..

1. 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 난이도(solved.ac 기준): 실버3 풀이 간단한 DP 문제다. DP 배열 값은, 이전 인덱스의 값에 + 이전 인덱스의 input값으로 받은 리스트 값을 더해주면 된다. 구간을 더해준 뒤 dp[목적지점] - dp[시작지점-1] 을 해주면 해결할 수 있다. 이 부분은 직접 dp값을 출력해보는 게 더 와닿을 것이다. 여기에서 sys.stdin.readline을 사용하지 않으면 무조건 시간 초과가 난다. 따라서 sys.stdin.readline을 반드시 써야 한다. 2. 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 난이도(solved.ac 기준): 실버1 풀이 1번의 구간..

링크 https://www.acmicpc.net/problem/1912 난이도(solved.ac 참고) 실버2 풀이 가장 큰 값이 음수라면 일단 더해봤자 값이 더 커질 수가 없으므로 그 값만 출력한다. 그게 아닐 경우에는 dp라는 배열을 따로 만들어서 첫 값으로는 input값을 받아서 만든 리스트의 첫번째 값을 반환하고 그 이후부터는 dp의 이전 인덱스 값과 input값을 받아서 만든 리스트 a의 현재 인덱스 값을 더한 게 양수인 경우에만 dp의 현재 인덱스에 값을 부여해주고 그게 아니라면 dp[i]는 0으로 그대로 남게 된다. 즉 더한 값이 0보다 작을 경우엔 0으로 초기화하여 다시 시작하는 과정을 반복한 것이다.