본문 바로가기

백준99

[백준] 2529 - 부등호 (Python) 문제 출처 : www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 문제 풀이 : 문제를 분할해서 생각해보자. 새로 추가되는 숫자에 대한 부등호 관계가 만족하는가? 새롭게 추가되는 숫자를 중복없이 어떻게 만들 것인가? 최소와 최대를 어떻게 구할 것인가? (따로 구분해주기) 위의 서브 문제들을 풀어가보자 새로운 숫자가 추가 될때 마다 앞에 숫자랑 비교해주는 함수를 만들자(check 함수) 백트래킹을 이용해보자. 숫자는 중복없이 0~9까지이므로 for문 돌려서 사용하면된다. 이때 .. 2021. 4. 2.
[백준] 2217 - 로프 (Python) 문제 출처 : www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 풀이 : 최대무게를 걸어야하고 , "몇 개"의 로프만 골라서 사용할 수 있다. 로프를 여러개 사용하는게 무게가 줄어들어서 좋을까? 라는 생각이 들 수 있지만 주의해야하는 것은 로프마다 견딜 수 있는 무게가 다르다는 점이다. 이런 점을 보았을때 로프를 내림차순으로 정렬 시킨후 모든 로프에 대해서 무게를 늘려가며 최대값을 갱신해주면된다. 제일 무거운 무게를 지탱할 수 있는 로프 순서대로.. 2021. 3. 30.
[백준] 1931 - 회의실 배정 (Python) 문제 출처 : www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 : 이 문제에서 살펴보아야할 점은 끝나는 시간과 시작하는 시간이 같다면 바로 시작할 수 있다는 점이다. 때문에 주어진 회의시간을 끝나는 시간, 시작 시간으로 정렬한 뒤에 가장 먼저 시작해서 짧은 거 순으로 넣으면 그것이 전체에서도 최대가 될 것이라고 생각한다. 앞쪽에서 시간을 조금 잡아 먹을 수록 뒤에서 고려해 줄 수 있는 것이 많기 떄문이다. 때문이 이것은 그리디로 풀 수 있다. n = int(input()) meeting = [] for i in range(n): start, end = map(in.. 2021. 3. 27.
[백준] 11053 - 가장 긴 증가하는 부분 수열 (C++) 문제 출처: www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이: 필자가 생각하기에 이 문제의 핵심은 증가수열의 첫 부분 정하기 뒷부분에서 만들어지는 증가 수열이 기존에 만들어진 증가수열의 일부분(중복되는 부분) 인지 체크 때문에 cache 자료구조를 만들어서 방문한 자리를 체크해주었다. 이렇게 해주어도 괜찮은 이유는 예제를 보면서 알아보자 arr 10 20 10 30 20.. 2021. 3. 26.
반응형

티스토리툴바