잡담연구소

배워갈 게 많은 문제라고 생각해서 특별히 별표 표시해둠 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net IDEA 맨 처음에는 단순히 ? 정렬한 후에 중앙값을 인덱스로 하는 배열값을 선택하면 되지 않나 라고 생각했는데 기본 sort를 사용하면 시간복잡도가 $nlog{n}$으로 시간제한 0.1초를 절대 넘기지 못할 거 같았다. 그래서 고민고민 해보다 다른 사람들의 블로그를 참고해서 풀었다. 엄청 신기했는데 running median algorit..

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net IDEA 배열을 triangle 이라고 하자. 그렇다면 cost배열에 triangle[i][j]에 도달하는데 걸리는 최대 비용을 저장해주자. 그림보다는 입력형태를 봐야 규칙이 보인다. 그림에선 대각선이지만 입력배열에서는 대각선이 아니기때문이다. 맨 처음 0번째일때는 따로 드는 비용이 없기 때문에 cost = triangle 이다. 열이 0일때 그림에서는 열이 0일 떄는 자신의 오른쪽 위에서 밖에 오지 못한다. 입력배열기준으로 생각해보면 열이 0일떄는 자신의 바로 위에서만 올 수 있다..

www.acmicpc.net/problem/15411541번: 잃어버린 괄호첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net문제 해석을 못해서 꽤나 애먹었다;; 괄호를 1개만 쳐야하는건지 , 여러개 쳐도 되는건지, 연속해서 나타난다는게 ++ 같은 건지 아니면 1 + 2 + 3 이런식인건지,,,, 테스트케이스도 1개밖에 없고 문제를 이해를 잘 못했다. 👉 결론적으로 괄호는 하나 이상! 여러개 칠 수 있다. 연속해서 연산자가 나오지 않는다는 건 1 ++ 2 같은 게 안된단 뜻 IDEA 1. 어떤 식으로 풀지 고민하기 전에 가장 먼저 입..

www.acmicpc.net/problem/16291629번: 곱셈첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.www.acmicpc.netIDEA 2630번 색종이 만들기 ( blahblahlab.tistory.com/63 ) 와 같은 문제다. 분할을 4등분이 아닌 9등분으로 해주면 된다. CODE #include #include #include using namespace std; int arr[3000][3000]; int k, m_count = 0, p_count = 0 , z_count = 0; void divide(int x, int y, int n){ //개수 세기 int p=0, z=0, m = 0; fo..

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net IDEA 두 공유기 사이의 최대 거리를 구하는 문제다. 거리는 1부터 시작해서 최대 정렬했을 떄 기준 arr[n-1] - arr[0] 까지이다. 거리는 단조증가한다 -> 거리에 대해서 이분탐색을 적용할 수 있다. 정렬 시 인접한 공유기 사이의 최단 거리 = 1 , 최장 거리 = arr[n-1] 이므로 start = 1 , end = arr[n-1]로 설정한다 ..

www.acmicpc.net/problem/75697569번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.netIDEA7576번 토마토 ( blahblahlab.tistory.com/69 ) 문제를 그냥 3차원으로 푸는거일 뿐이다. 아이디어는 똑같고 사방이 아닌 위아래까지 고려해 방향 6개를 고려하면 된다. CODE#include #include #include #include using namespace std; int n, m,h; int map[100][100][100]; int dx[] = { ..