https://www.acmicpc.net/problem/1945 1945번: 직사각형 첫째 줄에 직사각형의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점의 좌표 xbl, ybl과 오른쪽 위 꼭짓점의 좌표 xtr, ytr이 순서대로 빈칸 하나를 사이 www.acmicpc.net 교내 백준랜덤디펜스 8번. "원점을 지나는 직선" 이 힌트. 어떠한 점(x,y)과 (0,0) 사이 선을 그으면 그 선의 기울기는 y/x 임을 이용한다. 원점에서 그은 어떠한 직선이 직사각형을 지나려면 그 직선의 기울기가 직사각형의 왼쪽 위 꼭짓점에서 그은 선과 직사각형의 오른쪽 아래 꼭짓점에서 그은 선의 기울기 사이에 존재해야한다. 즉, 원점에서 그은 직선을 y=kx라고 ..

https://www.acmicpc.net/problem/16238 16238번: 독수리 첫째 날 1번 칸의 왼쪽에서 날기 시작해 2번 칸의 양을 먹는다. 독수리가 먹은 양의 수는 10마리이다. 2번 칸에 있는 양을 먹었기 때문에, 1번, 2번 칸의 양의 수는 0이 된다. 첫째 날의 밤에 양의 수 www.acmicpc.net 왼쪽 / 오른쪽에서 접근한다는 함정에 안 속아넘어가도록 조심해야하는 문제. 얼핏보면 순서에 굉장한 제약을 받을 거 같지만, 실제로 원하는 값들을 꺼내고자 할때 꺼내고자 하는 값들이 미리 결정된다면 그 값을 꺼내기 위한 최적의 방법은 유일해진다. 값 두개를 순서대로 꺼낼 때 왼쪽에서 접근한다면 더 왼쪽에 있는 값을 먼저 꺼내야 함은 자명하고, 오른쪽에서 접근한다면 더 오른쪽에 있는 값..

추천받아서 풀어본 그리디 문제. https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 처음에는 lis인가 생각했었는데 일단 이건 아니었다. 만약 swap 연산 후에 break 했다면 lis였을지도? 어떠한 숫자가 뒤로 가는 연산은 j 루프 한번으로 충분하기때문에 교환한 원소의 갯수를 기준으로 생각하면 정답에 도달하기가 힘들다. 어떠한 숫자 K에 대해서 swap을 진행한다고 할때, 지문에 나온 코드를 통해서 정렬하면 K는 j에 ..

https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 연속된 고정 길이의 회전초밥들을 골랐을때 + 고정된 한개의 메뉴가 있을때, 초밥의 종류를 최대한 다양하게 가져가도록 하는 문제 15961번은 범위가 매우 크기 때문에 브루트포싱으로 해결할 수 없고, 회전초밥의 길이가 고정적이라는 점에서 착안해서 슬라이딩 윈도우 알고리즘을 적용해서 문제를 해결했다. 초밥의 종류를 관리하는데에는 다양한 방법이 있을 수 있는데, ..

https://www.acmicpc.net/problem/5520 5520번: The Clocks Read nine numbers from the standard input. These numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. The example in figure 1 gives the following input data file: www.acmicpc.net 스터디 하면서 풀어본 문제. 일단 제일 처음 든 생각은, 시계를 돌릴때 4번 돌리면 아무 의미가 없어진다는것 시계를 돌릴수 있는 9가지 방법이 주어지는데, 이 9가지 방법 각각을 4n+m번 돌린 경우는 m번 돌..

깔끔하게 풀어내서 마음에 드는 문제 https://www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 정수X의 자릿수를 쪼개서 어찌저찌 만들어도 되겠다만, 문자열 S에 대해서 '0' ~ '9' 사이의 대소관계는 0~9 사이의 대소관계와 똑같이 계산할 수 있고, 문자열의 길이가 서로 다 같아서 문자열의 길이가 달라지는 경우도 고려 안해줘도 되기때문에 X를 정수로 입력받는것이 아니라 문자열 S로 받았고, 문자열 S는 요컨데 char형의 배열이라고 ..