문제1E-합 구하기2 - 알고리즘 문제해결기법 입문
알고리즘 문제해결기법 입문
    • 01
      About Course
    • 공부하는 방법
      문제 모범 답안
      수강생 전용 Slack
      공식 오프라인 강의
    • 02
      0. Introduction & Tutorial
    • 알고리즘과 자료구조
      문제 해결하기
      약속하기
      문제의 구성
      문제0A-출력해보기
      문제0B-입력받아보기
      문제0C-반복해보기
      문제0D-저장해보기
      문제0E-테스트케이스
    • 03
      1. 코드와 친해지기
    • 챕터1 강의노트 (임시)
      코드와 친해지기
      반복문과 친해지기
      문제1A-최대값 함수
      문제1B-배열의 최대값
      문제1C-카운팅하기
      문제1D-합 구하기1
      문제1E-합 구하기2
      문제1F-탐색하기1
      문제1G-탐색하기2
      문제1H-탐색하기3
      문제1I-선택정렬 구현하기
      문제1J-합 구하기3
      단원 되짚어보기 & 해설
    • 04
      2. 알고리즘의 연산량
    • 연산량과 시간복잡도
      챕터2 강의노트 (임시)
      실제 연산량 줄이기
      문제2A-도토리 키재기
      문제2B-오름차순인가?
      문제2C-다양성
      문제2D-문자열의 비교
      문제2E-소수의 판별
      문제2F-데스티니
      문제2G-버블정렬 구현하기
      문제2H-픽셀 수 세기
      문제2I-정주행
      문제2J-승부 조작
      단원 되짚어보기
    • 05
      3. 공간 활용하기
    • 배열의 특징
      챕터3 강의노트(임시)
      배열 활용하기
      문제3A-전화번호
      문제3B-페인트
      문제3C-응모
      문제3D-피보나치 나머지
      문제3E-색종이
      문제3F-과유불급
      문제3G-팬미팅
      문제3H-두 카드
      문제3I-세 카드
      문제3J-네 카드
    • 06
      4. 자주 사용되는 수학 알고리즘
    • 챕터4 강의노트(임시)
      문제4A-스도쿠 보드
      문제4B-Probing
      문제4C-최대공약수와 최소공배수
      문제4D-수열의 순환
      문제4E-소인수 분해
      문제4F-소수 세기
      문제4G-배열 흔들기
      문제4H-카잉 달력
      문제4I-골드바흐의 추측
      문제4J-공약수 게임
    • 07
      5. 구현 훈련하기
    • 문제5A-놀이 공원
      문제5B-거대 놀이 공원
      문제5C-레이저 타워
      문제5D-레이저 타워 건설하기
      문제5E-숫자 채우기1
      문제5F-숫자 채우기2
      문제5G-숫자 채우기3
      문제5H-두 직사각형
      문제5I-두 선분
      문제5J-로봇 청소기
      문제5K-고성능 로봇 청소기
      문제5L-NBA농구
      문제5M-와일드 카드
      문제5N-패턴 검사
      문제5O-단어 퍼즐
      문제5P-이름 짓기
    • 08
      6. 자료구조 활용하기
    • 챕터6 강의노트 (임시)
      문제6A-괄호 문자열
      문제6B-탑
      문제6C-히스토그램
      문제6D-조세퍼스 문제
      문제6E-폭탄 제거
      문제6F-폭탄 제거 순서 정하기
      문제6G-불안정 지역
      문제6H-중복 제거하기
      문제6I-정사각형
      문제6J-빈도수 세기
      문제6K-시장 추천하기
      문제6L-배열 합치기
      문제6M-이중 우선순위 큐
      문제6N-중앙값 큐
      문제6O-피자 하와이
    • 09
      7. 재귀 함수와 분할 정복
    • 챕터7 강의노트(임시)
      [문제07A] 모든 조합 출력하기
      [문제07B] 하노이의 탑
      [문제07C] 단지 번호 붙이기
      [문제07D] Merge Sort 구현하기
      [문제07E] Quick Sort 구현하기
      [문제07F] 히스토그램
      [문제07G] Counting Inversion Pairs
      [문제07H] Finding Closet Pair
    • 10
      8. DFS/BFS
    • 챕터8 강의노트(임시)
      [문제08A] - 그래프의 탐색 1
      [문제08B] - 그래프의 탐색 2
      [문제08C] - 그래프의 최장 경로
      [문제08D] - 그래프의 최단 경로
      [문제08E] - 바이러스
      [문제08F] - 미로 탈출하기
      [문제08G] - 토마토
      [문제08H] - 소수 경로
      [문제08I] - 스도쿠 보드 채우기
      [문제08J] - N Queen
    • 11
      9. 그래프 알고리즘
    • 챕터9 강의노트(임시)
      [문제09A] 해밀턴 경로
      [문제09B] 외판원 순회 문제
      [문제09C] 한 붓 그리기
      [문제09D] 그래프의 연결성
      [문제09E] 최소 신장 트리 1
      [문제09F] 최소 신장 트리 2
      [문제09G] 그래프의 최단 거리
      [문제09H] 그래프의 최단 거리 2
    • 12
      10. 동적 계획법
    • [문제10A] 가장 긴 부분 증가수열 (LIS)
      챕터10 강의노트(임시)
      [문제10B] 팬스 수리하기
      [문제10C] 아르바이트
      [문제10D] 회선 설치하기
      [문제10E] 2차원 누적합
      [문제10F] 퀼팅(Quilting)
      [문제10G] 가장 긴 공통 부분 문자열 (LCS)
      [문제10H] Ah-choo!
      [문제10I] 곱하기는 귀찮아
      [문제10J] 올바른 괄호 문자열
      [문제10K] 배낭 문제 (Knapsack Problem)
      [문제10L] 7 Segment Display
    • 13
      11. 문제를 푸는 다른 방법
    • 챕터11 강의노트(임시)
      [문제11A] 지하철을 빠르게 빠르게
      [문제11B] 감시 로봇
      [문제11C] 복도 통과하기
      [문제11D] Selling Cells
      [문제11E] 인구조사
      [문제11F] 그래프 최소 분할
    • 14
      12. 문자열 알고리즘
    • 챕터12 강의노트 (임시)
      [문제12A] Rabin Karp
      [문제12B] KMP
      [문제12C] 실패함수 계산하기
      [문제12F] Trie 구현하기
    문제1E-합 구하기2
    배우기
    실습 내용
    배우기
    문제1E-합 구하기2
    단순히 카운팅하는 것을 넘어 합을 구하는 방법을 고민해봅시다.
    실습 내용

     사막 여우의 탈을 쓴 지수는 놀이공원에서 아르바이트를 하고 있습니다. 지수가 담당하고 있는 놀이기구는 무게에 민감하기 때문에 몇 가지 제한을 두고 있습니다.

    • 이 놀기기구는 몸무게가 P kg이 넘는 사람은 탑승 할 수 없습니다.
    • 그리고 탑승한 승객의 몸무게의 총 합은 Q kg을 넘을 수 없습니다.
    • 다만 탑승하는 인원의 제한은 두고 있지 않습니다.

     보통은 놀이기구의 최대 탑승 중량을 넘기 전에 탑승 인원을 나누기 때문에 크게 문제가 발생하지 않습니다. 하지만 오늘은 조금 문제가 있습니다. 아주대학교 알고리즘 동아리라고 자신들을 소개한 단체손님 때문입니다. 그들은 애초에 몸무게가 P kg를 넘어가는 회원은 제외하더라도 나머지 인원들은 꼭 함께 놀이기구를 탑승해야한다고 우기고 있습니다. 이 동아리의 회원들 중 놀이기구를 탈 수 있는 사람은 몇 명인지, 그리고 체중 제한을 통과한 사람들은 모두 함께 놀이기구를 탈 수 있는지 계산할 수 있는 프로그램을 작성해주세요.


    입력 형식

     첫 줄에 세 자연수 N, P, Q가 주어진다. 각각 동아리 회원의 수 N, 놀이기구의 탑승 제한 체중 P, 놀이기구의 최대 하중 Q이다. 

    그리고 두 번째 줄에는 각 회원의 몸무게가 주어진다. 

    • N는 10,000이하의 자연수이다.
    • P와각 동아리 회원의 몸무게는 1이상 300이하의 자연수이다.
    • Q는 3,000,000이하의 자연수이다


    출력 형식

     첫 줄에 놀이기구 체중 제한에 걸리지 않은 회원의 수와 그들의 몸무게의 총 합을 공백으로 구분하여 출력한다.

    그리고 두 번째 줄에 그들 모두가 함께 놀이기구에 탑승할 수 있는지 여부를 YES 혹은 NO로 출력한다.


    문제 출처

    입/출력 예시
     
    :
    공백
    :
    줄바꿈
    예시 1
    입력
    10 80 500
    75 50 67 84 54 67 98 85 58 90
    출력
    6 371
    YES
    ⋇ 입출력 형식을 잘 지켜주세요
    배우기
    실습 내용
    Q & A
    궁금한 점이나 수업 내용 중 어려웠던
    부분에 대해 질문해보세요.
    이 강의에 관한 질문(0)