메이쁘

https://www.acmicpc.net/problem/1159 1159번: 농구 경기 문제 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 www.acmicpc.net 진짜 오랜만에 다시 백준 문제를 풀기 시작했다. 복귀 문제?! 쉽기 때문에 별도의 해설 및 알고리즘 설명은 생략하겠다. 간단하게 말하자면, 같은 문자의 개수를 파악하는 문제들은 'a', 'A' 와 같이 시작 문자의 아스키코드를 파악하여 (여기서는 'a' 가 시작문자이므로, 'a' 는 97 이다.) 해당 문자 - 'a' 를 배열의 index로 보고 해당 index의 원소를 counting하면 된다. 만약,..

https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 문제 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. � www.acmicpc.net 이진 탐색 분류로 되어있는데 그리디로 해결한 문제. 생각보다 쉽지만 처음 규칙을 찾는데 조금 걸렸다. 핵심은 - 시작 인덱스를 1로 가정하고, 입력받은 책의 맨 앞에서부터 끝까지 하나씩 시작 인덱스와 비교한다. - 비교했을 때, -> 시작 인덱스 + 1 보다 더 크다면 -> 해당 값 과 시작 인덱스 차이만큼 별도 값에 더한 후, 시작 인덱스를 해당 값 으로 변경한다. -> 시작 인덱스 +..

https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 www.acmicpc.net 착한 제목에 그렇지 못한 문제.. 이진탐색 보다는 탐욕에 가까운 문제로 골머리 한시간 썩히다가 해설을 참고하니 그리디로 더 쉽게 풀 수 있었다. 핵심 - 못 주는 사탕의 개수는 고정되어 있다. M개의 사탕을 줄 수 있고, 각 사람들이 원하는 사탕의 개수 총합을 SUM 이라고 할 때 못 주는 사탕의 개수 = SUM - M - 위에서 못주는 사탕의 개수로 공략한다. 이 때, 분노게이지를 낮추기 위해선 한..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B�� www.acmicpc.net 이분 탐색 문제인데 정답률에 비해 난이도는 높았었던 문제. 진짜 생각이 안나서 해설을 참고했었다. 핵심은 이거다. - 정렬된 배열 : K번째에 해당할 것 같은 수 (행렬 내 범위. 1 ~ K) *** 최댓값을 n * n 이 아닌 K로 잡는 이유는 K번 째에 해당하는 수는 절대 K를 초과하지 않기 때문에 탐색 시 시간 절약을 위해서다. *** K를 초과하지 않는 이..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 문제 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 �� www.acmicpc.net 이진 탐색 문제이다. 한글 번역이 헷갈리게 되어있어 문제 풀이 또한 헷갈렸었다..ㅠㅠ 하지만 타 문제에 비해 어렵진 않았던 문제. 핵심 - 돈이 남아도 횟수(M) 를 채우기 위해 넣고 빼기 가능. -> 이 말은 즉슨, M번 이하만 채워도 M번과 동일하게 임의로 넣고빼면서 맞출 수 있다. -> M번 이하인 인출 비용 중 최솟값 구하기. - 정렬된 배열 : 인출 금액 (1원 ~ 최대 사용 금액 * M ..

https://www.acmicpc.net/problem/3079 3079번: 입국심사 문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관�� www.acmicpc.net 이진 탐색 문제이다. 중요한 점이 있다면 심사대가 비었다고 바로 심사받는 것이 아니라, 자율적으로 쉬면서 바로 안가도 된다 는 것이다. 그렇기 때문에 이진탐색을 사용한다. - 정렬된 배열 : 모든 M명이 심사받는 데 걸린 시간 (1초 ~ 심사 최장 시간 * M명 초) - 구하는 방법 : mid 초 / 각 심사대 심사 시간 -> mid 초 내에 해당 심사대에서 심사받을 수 있는 최대 인원 수 - 그래서,..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 이진탐색과 BFS가 섞인 문제이다. 구하려는 값 : 두 공장의 이동중량 최댓값. 두 공장의 이동중량 : A공장에서 B공장까지 이동하는데 A공장에서 싣은 무게로 B공장까지 갈 수 있는 무게를 뜻함. 범위가 극도로 넓고, 시간 제한이 1초 이며 최댓값을 구하라는 뜻은 한 값이 아닌 여러 값이 정답으로 나올 수 있다는 뜻 이기 때문에 이진탐색을 사용했다...

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 문제 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 www.acmicpc.net 이분탐색 문제이다. 도저히 고민하다가 못풀겠어서 풀이 방법을 살짝(많이) 보고 이해한 다음 해결했다.. 이분탐색 어렵다. 계속 관련 유형 문제들을 풀어봐야겠다. 핵심은 문제에 있다. 1. 모든 보석을 N명의 학생들에게 나눠줘야 한다. 모든 보석이다. 하나라도 남으면 안된다. 2. 보석을 받지 못하는 학생이 있어도 된다. 즉, 모든 보석을 나눠줘야 하지만 한명당 꼭 하나 이상씩 나눠줄 필요는 없다. ..

https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 기본 백트래킹 문제. K 개 중 중복없이 6개를 뽑아서 사전순으로 정렬해서 출력하는 문제 이다. 근데 말이 사전순 정렬이지 백트래킹을 사용할 때, 앞에서부터 순차적으로 탐색하면 자동적으로 사전 순 정렬이 된다. 즉, KP6 을 구하는 문제. 이를 백트래킹으로 순열 함수를 구현하면 된다. 자세한 사항은 하단 소스코드 를 참고해주세요. 감사합니다. 소스코드

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 브루트 포스 문제. 순열 을 사용했다. 순열을 통해 부호를 순차적으로 선택하며, 선택할 때 마다 차곡차곡 계산해서 패러미터로 담아 재귀호출한다. 그래서 모든 부호를 선택한 경우에 지금까지 계산한 결과값들 중 최솟값을 찾아 출력하면 끝! 더 자세한 사항은 아래 소스코드를 참고해주세요. 감사합니다. 소스코드