개발자 퉁이리

www.acmicpc.net/problem/2884 2884번: 알람 시계 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 사칙연산 ⊙ 문제 접근 과정 풀던 문제가 너무 안 풀려서 머리 식힐 겸 이 문제를 풀어봤다. h와 m값을 입력받는다 m에서 45분을 바로 빼준다. 만약 m이 음수가 되면 60분을 더해주고 h에서 1을 빼준다. 만약 1을 뺀 후 h가 음수가 되면 24시간을 더해준다. h와 m 출력 ⊙ 문제 풀이 #include using namespace std; int ..

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 이분 탐색 해시를 사용한 집합과 맵 ⊙ 문제 접근 과정 vector를 활용해 값을 입력받고 제일 먼저 해야 할 건 정렬이다. sort로 정렬을 해주고 algoritm 헤더에 있는 Lower bound와 Upper bound 알고리즘을 사용하면 된다. 참고로 sort도 algoritm 헤더에 있다. 그냥 제출..

www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 ⊙ 문제 접근 과정 1부터 n까지의 공식인 n*(n+1)/2를 이용하면 짧은 줄로 풀 수 있다. 하지만 퉁이리는 for문을 사용했다. int로 계속 사용해서 오답이라구 나왔었는데 long long type으로 변경해주니 바로 해결할 수 있었다. 혹시 정답이 맞는데 틀리다고 계속 나온다면 type을 의심해보자. ⊙ 문제 풀이 #include using namespace std; typedef long long ll; int main() { ll s; cin>>s; ..

www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 정렬 이분 탐색 ⊙ 문제 접근 과정 코드는 tooo1.tistory.com/122과 거의 똑같다. [백준(BOJ)] 1920번 : 수 찾기 - C++[CPP] www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 ..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 최적화 문제는 일단 이진 탐색을 떠올리자. M만큼의 나무를 가져가면서 절단기로 설정할 수 있는 높이의 최댓값을 구하는 문제이다. 시작 값은 0, 끝 값은 입력받은 값 중 가장 큰 값으로 설정했다. 그리고 이진 탐색으로 범위를 좁혀 문제를 해결했다. ⊙ 문제 풀이 #include #i..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 문제를 보고 이진 탐색으로 접근해야겠다고 생각했다. 순차 탐색으로 문제를 접근하면 시간 복잡도가 O(N)이다. 그렇지만 이진탐색으로 접근한다면 시간 복잡도를 O(logN)으로 줄일 수 있다. 이진 탐색을 STL 라이브러리를 이용하지 않고 직접 구현하여 문제를 풀어봤다. ⊙ ..

www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 배치하는 문제를 만났을 때, 가장 중요한 포인트는 기준이다. 기준을 잡고 풀이를 하면 훨씬 편하다. 그렇다면 이 문제에서는 기준을 어떻게 잡는 것이 좋을까? 정답은 오름차순으로 정렬하라고 하였으니 오름차순으로 가장 길게 정렬된 부분을 기준으로 하자 만약 LIS(최장 부분 증가수열)을 알고 있다면 문제를 더 편하게 풀 수..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 슬라이딩 윈도우 ⊙ 문제 접근 과정 그렇게 어렵지는 않은 문제다. 공간 복잡도를 조금만 신경 쓴다면. 메모리 제한이 4MB이기에 공간을 잘 사용해야 한다. 변수를 여러 개 설정해주고 매번 갱신해 공간을 절약하는 방법을 선택했다. 아래 예시를 통해 접근 과정을 알아보자. 3 1 2 3 4 5 6 7 8 9 N=3, 3줄을 입력받는다. 첫 번째 줄은..

www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 ⊙ 문제 접근 과정 문제를 보고 제일 먼저 잔돈을 배열로 정리했다. 그다음 무한 루프 문을 만들고 배열 인덱스를 활용하여 count를 올려주고 break를 통해 탈출하는 반복문 코드를 짰다. 배열을 이용하여 잔돈 정리 count 값 초기화 index를 활용해 입력받은 값 비교 입력받은 값이 더 크면 잔돈을 빼고 c..

www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 ⊙ 문제 접근 과정 조건에서 입력도 무작위가 아닌 친절하게 오름차순으로 정렬하여서 입력하라고 한다. 막힘없이 코드를 작성했고 예제 입출력과 같은 값을 출력할 수 있었다. 하지만 틀렸다고 떴다. 아래 코드이다. #include using namespace std; int m..