https://www.acmicpc.net/problem/1497 1497번: 기타콘서트 첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 www.acmicpc.net 1. Logic 입력 자체가 n = 1; } return cnt; } void solve(int idx, long long bit, int cnt) { int bitToSong = countBit(bit); if(bitToSong > maxCnt) { maxCnt = bitToSong; ans = cnt; } else if(bitToSong == maxCnt) { ans = min(ans,..
Algorithm
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 1. Logic 1부터 계속 더하다가 처음으로 N을 넘는 숫자가 나오면 그 숫자에 -1 한 값이 정답이 된다. 2. Code #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); long long S; cin >> S; long long sum = 0, num = 1; int cnt = 0; while (1) { sum += num; cnt++; if (sum > S) { cnt--; break; } num++; } cout
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 1. Logic 0~n-1까지 순회하면서 각 시작 위치보다 큰 숫자만 더해주면서 최댓값을 구해주면 된다. 코드를 보면 이해가 쉬울 것 이다. 2. Code #include using namespace std; int n; vector input; //증가하는 부분수열의 합 int dp[1001][1001]; int solve(int id..
https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 1. Logic 중복을 포함하지 않는다고 했기 때문에 map대신 unordered_map을 사용했다. 그리고 입려이 50만이기 때문에 logN을 시간복잡도로 가지는 map에 비해 O(1)을 가지는 unordered_map을 사용하는게 좋을 것 이라고 생각했따. unordered_map의 key:학번 value:클릭한 순서 로 설정하고 입력은 받은 후 vector 로 설정하여 원소를 넣..
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 1. Logic 입력이 1000000이기 때문에 시간복잡도가 logN인 map을 사용해서 입력을 받았다. 2. Code #include using namespace std; map m; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int ..
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. Logic 물에 잠기지 않는 지점이 최대가 될 때를 구하는 문제이다. 처음에 이 문제를 봤을 때 그냥 주변높이 보다 높으면 안전지역인줄 알았는데 문제를 다시 읽어보니 0~최대 높이까지 확인하면서 그중에 가장 많은 안전지역의 갯수를 구하는 문제이다. 풀이 방법은 입력을 받으면서 최대 높이를 구하고 0~최대 높이 까지 BFS를 돌면서 최대 안전 지역의 갯수를 구하면 된다. 2. Code #include..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 1. Logic 1. pair를 원소로 가지는 stack 하나를 선언한다. pair는 이다. 2. 현재 입력받은 키보다 작은 애들은 무조건 볼 수 있기 때문에 pairCnt를 올려주고 어짜피 나보다 작은애들이기 때문에 나보다 큰 애가 들어오게 되면 내 뒤의 작은애는 보지 못하기때문에 스택에서 pop해주고 다시 넣어주지 않는다. > 이 방식으로 스택을 항상 내림차순으로 정렬해..
https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1. Logic 남학생은 배로수 바꿔주면 쉽지만 여학생이 문제이다. 여학생이 받은 번호 기준으로 왼쪽 오른쪽이 같으면 바꿔주고 다르면 바꿔주면 안된다. 그래서 while문의 조건을 swit[start] == swit[end]로 잡아줬다. 그리고 20개마다 줄 바꿔주는것을 잘 신경쓰면 된다! 2. Code #include using namespace std; int n, m; bool swit..
https://www.acmicpc.net/problem/25757 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 1. Logic 임스와 lms는 다른 사람이라는거에 유의해서 입력을 받고 Map에 없으면 카운트해주고 있으면 넘어가준다. 코드를 보면 쉽게 이해가 갈 것이다. 2. Code #include using namespace std; map name; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cou..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 1. Logic - check배열을 만들어서 리턴된 수는 생성자가 있는 숫자이기 때문에 체크를 해서 check배열이 true인 숫자들만 출력해주면 된다. 2. Code #include using namespace std; bool check[10001]; int cur(int num) { int sum = num; while(num != 0) { ..
