Algorithm/Algorithm Problem

백준 16943 숫자 재배치(순열, 구현)

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 간단하지만 표현할 수 있는 방법이 많아 시간을 많이 쓴 문제 였다. permutation을 한 다음 숫자를 하나씩 비교해서 갱신하면 되는 문제다. 여기서 point는 permutation 라이브러리를 써서 순열을 만들면 작은 수부터 순서대로 저장되는게 아니다. 0으로 시작하는 수는 제외하고 순열을 탐색하면서 b보다 작은 값들에서 max값을 갱신 시키면 된다. from ite..

백준 1911 흙길 보수하기(구현,그리디)

https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1

백준 15729 방탈출(그리디)

https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 버튼을 누르면 오른쪽 2번째 까지 같이 눌리는 시스템이다. 버튼을 최소로 누르면서 결과값을 맞춰야하기 때문에 그리디적으로 접근을 해야했고 직접 몇개 그려서 보니까 i번째 버튼을 누르면 i를 포함해서 그전에 있는 버튼은 다시 누를 필요가 절때 없다.(그리디) 따라서 for를 n의 크기만큼 탐색하면서 temp = [0] * n 을 하나 만들고 똑같이 만들어질 때 까지 cnt를 늘리면 되는 문제다. n = int(input()) data = list(map(i..

백준 2072 오목(구현)

https://www.acmicpc.net/problem/2072 2072번: 오목 19x19크기의 바둑판에, 돌을 놓을 좌표가 주어지면 이 게임이 몇 수만에 끝나는 지를 알아보려고 한다. 사용하고자 하는 바둑판의 모양은 위의 그림과 같으며, (1, 1)이 가장 왼쪽 위의 좌표이고 (19 www.acmicpc.net 처음엔 간단하게 돌을 놓은 순간 board 전체를 탐색해서 5칸이 이어진 구간이 있으면 그 순간의 i를 출력하는 간단한 문제로 생각했다. 하지만 이러한 경우 때문에 생각외로 잘 풀리지 않아 많은 시도를 한 후에 겨우 풀었다. 저런 조건때문에 탐색을 시작한 지점(x,y)에 대해 8방향까지 (x+5,y+5) 이렇게 탐색 하는 방법은 올바르지 않은 탐색이다. (x,y)로 부터 8방향을 탐색하는데 ..

백준 11000 강의실 배정(Heap, 우선순위 큐)

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 처음에는 이문제와 비슷하다고 생각했는데 미묘하게 다른점이 난이도를 증가시켰다. https://www.acmicpc.net/problem/17262 17262번: 팬덤이 넘쳐흘러 선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬 www.acmicpc.net 강의실을 최대한 추가 안하고 최소한의 강의실을 추가하는..

백준 13900 순서쌍의 곱의 합(구현)

https://www.acmicpc.net/problem/13900 13900번: 순서쌍의 곱의 합 첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000) 두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다. www.acmicpc.net n의 범위가 100000이기 때문에 combination으로 풀면 안된다는것을 바로 알았다. 근데 어떻게 풀지를 몰라 한참을 고민하다가 리스트에 있는 값을 변수화 시켜서 구하는 과정을 해봤더니 list = [a,b,c,d] a(b+c+d) + b(c+d) + cd 이런식으로 규칙이 보이기 시작했다. 구현문제는 항상 어떠한 규칙을 찾아내야 하는데 쉬워보여도 생각이 잘 나지않아 어려운 것 같다. n = i..