본문 바로가기

백준189

백준 1562 c++ "계단 수" -PlusUltraCode- https://www.acmicpc.net/problem/1562 [필자 사고] 어려운 문제다.처음에 DNS를 이용하여 풀려고 했지만 경우의 수를 생각해보니 시간초과가 나온다.어쩔 수 없이 30분 고민하고 풀이 힌트를 보았더니 비트마스킹을 이용한 동적프로그래밍 문제다. 나는 처음으로 비트마스킹 알고리즘을 만나게 되었따. 간단히 말하자면1000000000 이라는 2진수로 이루어진 bit가 있고1위의 기존 bit | new bit 를 하게 되면1000010000 식으로 게임 처럼 1로 바껴서 on모드가 된다.이러한 방식으로 아래의 문제를 해결했다.   소스코드 해설은 아래와 같다 1.코드 개요이 코드는 숫자의 길이 N이 주어졌을 때, 계단 수를 계산하는 프로그램입니다. 계단 수는 숫자의 각 자릿수가 1씩 증.. 2024. 12. 26.
백준 1806 c++ "부분합" -PlusUltraCode- https://www.acmicpc.net/problem/1806 [필자 사고]투포인터 알고리즘을 이용하여 푸는 문제이다. 문제에서 주어진 조건중 조심해야 될 것은 아래와 같다. S의 범위가 1억이라는 점이다.브루스트 알고리즘을 이용하면 시간초과를 보게 될 것이다.또한 자료형 int 가아닌 long을 사용해야 된다. sum을 기준으로 S보다 작으면 endIdx를 키우고그렇지않으면 startIdx를 이동시키는 방식으로 코드를 구현했따. 아래는 코드 해설이다 전역 변수 및 배열 정의코드에서는 Arr라는 벡터를 통해 각 구간(또는 노드)의 값을 저장하고, N은 배열(또는 그래프)의 크기, S는 목표로 하는 합의 최소값을 나타낸다. Input 함수는 사용자 입력을 통해 배열의 값과 필요한 변수들을 초기화한다.2.. 2024. 12. 25.
백준 1202 C++ "보석 도둑" -PlusUltraCode- https://www.acmicpc.net/problem/1202 [필자 사고]이 문제는 크게 sort 와 우선순위 큐를 활용하여 문제를 해결 했다. 필자는 우선순위 큐를 처음에 생각 못하여 binary_Search() 를 진행했지만 실패했다. 필자는 다음과 같은 사고 과정으로 문제를 해결했다. 가방의 무게는 오름차순으로 정렬한다.보석 배열은 값어치 순이 아닌 무게 순으로 오름차순으로 정렬한다. while 문을 실행하여 가방을 기준으로 보석들의 무게가 가방의 담을 수 있는지 점검하고 담을 수 있다고 하면우선순위 큐에 넣는다.우선순위 큐에 넣어진 값은 보석의 값어치가 높은순으로 정렬되어 있어매번 하나의 가방을 검사할 때마다 가장 높은 값어치를 꺼내 sum에 더한다. 여기서 필자는 처음 의문이 들었다.다른 .. 2024. 11. 14.
백준 1005 c++ "ACM Craft" -PlusUltraCode- https://www.acmicpc.net/problem/1005 [필자 사고]이 문제는 위상정렬 문제이다.다른 위상정렬 문제와 다른 이 문제만의 특이점은 아래와 같다. 자신이 걸리는 건물의 시간과이 건물을 짓기 위한 그 동안의 시간을 더해야 된다는 점이다. 필자는 자신이 걸리는 건물의 시간은 마지막에 더하는 방식으로 진행하였따.그 동안의 시간을 더하는 방식은 max함수를 이용하여 더 오래 걸리는 건물시간을 우선순위로 정했다. 아래는 소스코드 해설이다.  초기화 및 입력 처리:initVec(int N) 함수는 각 벡터(makeTime, dCount, linkArr, resultTime)를 크기 N+1N+1N+1로 초기화합니다.입력 함수 Input()은 각 테스트 케이스에 대해 프로젝트 개수 NNN과 관계.. 2024. 11. 10.

티스토리툴바