Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 풀이 음식들의 영양소를 모두 입력받은뒤에, 백트래킹을 이용하여 해당 음식을 선택했을때와 , 선택하지 않았을때의 경우를 모두 고려하여 매 함수 진입마다 최솟값을 갱신해주면된다. 시간복잡도 N개의 음식마다 선택의 길이 2가지 경우이므로, O(215)가 된다. 코드 #include #include #include #define MAX 987654321 using namespace std; //영양소 ..

2021. 9. 6.

문제풀이/백준oj

https://www.acmicpc.net/problem/6209 6209번: 제자리 멀리뛰기 첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다. 두 www.acmicpc.net 풀이 https://khu98.tistory.com/257 [프로그래머스] 징검다리 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개.. khu9..

2021. 9. 3.

문제풀이/백준oj

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 스택을 이용해서 문제를 해결할것이다. 오른쪽에 있는 수중에 자신보다 큰 가장 왼쪽에 있는수를 구해주어야 하므로, 오른쪽에서 왼쪽으로 탐색을 할것이다. 2번 입출력 예시를 가지고 설명을 해보겠다. 4 3 5 2 7 먼저 7의 오른쪽엔 아무것도 없기때문에 ,4번째 Result는 -1이 되고, 스택에 자신의 수를 쌓는다. 여기서 스택은 자신의 오른쪽에 있는 수들이라 생각을 하자. 그다음 수를 보자. 2를 기..

2021. 9. 2.

문제풀이/백준oj

https://www.acmicpc.net/problem/22993 22993번: 서든어택 3 좋은 전투 순서가 존재해서 준원이만 생존하고 나머지 플레이어가 모두 죽게 만들 수 있다면 Yes를, 반대로 전투가 어떤 순서로 이루어져도 준원이가 절대 최후의 생존자가 될 수 없다면 No를 www.acmicpc.net 풀이 준원이에게 가장 좋은 순서가 되기위해선, 공격력이 가장 작은 플레이어부터 차례대로 와가지고, 준원이에게 흡수되는것이 가장 좋은 순서이다. 따라서 준원이를 제외한 다른 플레이어들을 오름차순 정렬을 한 뒤, 앞에서부터 비교해가며 1. 준원이보다 공격력이 작다면 준원이에게 흡수, 마지막 플레이어까지 흡수했다면 True 2. 준원이보다 크거나 같다면 False 를 리턴해주면된다. 시간복잡도 정렬은 ..

2021. 9. 1.

문제풀이/백준oj

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 dp[i][j]=k 라고 할때, i번째열에서 j번째 스티커를 골랐을떄 ( 0 = 첫번째 스티커 / 1 = 두번째 스티커 / 2 = 아무것도 선택 x ) 0번째~i번째 열까지의 스티커점수의 최댓값을 k라고 하자. 먼저 1. i번열에서 첫번째 스티커를 고르기 위해서는 i-1번 열에서 두번째 스티커를 고른경우와 i-1번 열에서 아무것도 고르지 않은 경우가 있다. 이 두 경우중에서 더 큰..

2021. 8. 31.

문제풀이/백준oj

https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀이 N의 값이 매우 작으므로, 완전탐색을 이용해서, 겹치지 않게 서로다른 위치에 3개를 놓을때마다 최솟값을 갱신하는 방법으로 값을 구했다. 보통의 완전탐색과 같은데, 이제 꽃을 심으면 동,서,남,북,중앙 5군데를 차지하므로, 이것을 고려해서 문제를 해결해주면 된다. 코드 #include #include using namespace std; int maze[10][10]; bool flower[..

2021. 8. 30.

문제풀이/백준oj

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 입력받은 이름들을 숫자로 매핑해준뒤, Find-Union 알고리즘을 이용해서 네트워크를 연동시켜준다. 이때, 연결하고 카운팅을 하면 시간초과가 날 수 있으므로, 네트워크를 연결함과 동시에, 부모노드에 다른하나에 연결된 노드의 cnt를 더해준뒤, 부모노드의 cnt를 리턴해주면 시간초과가 나지 않고 값을 바로 구할 수 있게된다. 또한, 친구관계를 최대 100,000개 입력받는다 했으므..

2021. 8. 29.

문제풀이/백준oj

https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 풀이 먼저, 우리가 바꿀 수 있는것은 열이다. 열을 k번 바꾼뒤 각 행들을 모두 검사해서 켜진 행들의 최댓값을 찾아야 한다. 행을 하나하나 차례대로 검사를 하며, k번을 스위치를 누름으로 해당행이 켜진다면, 해당 행과 같은 모양의 행은 모두 켜진다. 예를들어 101 010 101 이 있고, k=1 이라고 해보자. 그럼 1번째 행을 보면 2번째 열의 스위치를 누르면 111로 모두 켜진다. k..

2021. 8. 28.