본문 바로가기

분류 전체보기

 (99)
[백준] 18870번 좌표압축 C++ 문제풀이 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 풀이 이 문제는 받은 값들을 정렬해서 인덱싱하고 난 뒤 바뀐 값들을 원래 순서대로 출력하는 문제였다. 맨 처음에 별 생각 없이 코드를 작성했더니 시간초과가 나왔다. 그래서 생각한 방법은 pair 를 이용해 first에는 입력값을 저장하고, second에는 기존 배열의 순서를 저장했다. first 값을 기준으로 배열을 정렬한 뒤, cnt라는 ..
[백준] 1427번 소트인사이드 C++ 문제풀이 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 String으로 수를 받은 후 하나씩 슬라이싱해서 벡터에 저장했다. sort함수를 이용해 정렬하고 결과를 출력하는 간단한 문제였다. 소스 코드 #include #include #include #include using namespace std; vector num; bool compare(int a, int b) { return a > b; } int main() { string N; cin >> N; for (int i = 0; i < N.size(); i++) { st..
[백준] 15686번 치킨 배달 C++ 문제풀이 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 풀이 완전탐색 문제였다. 맨 처음에는 재귀부분에 visited 배열을 만들어서 방문을 안 한 경우에 대해서 재귀를 수행했는데 시간초과가 나왔다. for (int i = 0; i < chicken.size(); i++) { if (visited[i] == false) { visited[i] = true; ch_chck.push_back(chicken[i]); dfs(cnt..
[백준] 14501번 퇴사 C++ 문제풀이 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 완전탐색 문제여서 모든 경우를 고려했다. 그 날의 상담을 수락하는 경우와 그 날의 상담을 하지 않고 그냥 다음 날로 넘어가는 2가지 경우로 나누어 진행했다. DFS를 이용해 상담을 수락하는 경우는 상담이 끝나는 다음 날로 이동하고, 아닌 경우는 다음 날로 이동하게 코드를 작성했다. 소스 코드 #include using namespace std; int money[21] = { 0 }; int day[21] = { 0 }; int N; int max_num = 0; void dfs(int d, int m) { if (d > ..
[백준] 2503번 숫자 야구 C++ 문제풀이 https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 문제 풀이 두 수의 자리수를 비교하는 경우 string으로 변환해서 비교하는게 편해 string으로 변환한 후 자리수를 비교했다. '1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수'라는 조건이 있어 0이 있거나 중복된 수는 고려하지 않고 완전탐색 방식으로 답을 구했다. 소스 코드 #include #include ; using namespace std; string num[101]; i..
[백준] 1300번 K번째 수 C++ 문제풀이 https://www.acmicpc.net/problem/1300 문제 풀이 처음 문제 풀이에서는 Symmetric 행렬의 특성이 뭐가 있나 고민해봤는데 딱히 결론이 나오지 않았다... 다른 분들의 블로그를 참고해보니 이분검색으로 Mid 보다 작은 숫자들의 수를 세어서 그 합이 K보다 크면 작은 쪽을, 그 합이 K보다 작으면 mid보다 큰쪽을 검색하는 식으로 진행하는 문제였다. 소스 코드 #include using namespace std; int main() { long long N, K; cin >> N >> K; long long max_idx = K; long long min_idx = 1; long long result = 0; while (min_idx
[백준] 2108번 통계학 C++ 문제풀이 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 풀이 이 문제 풀 때 어려웠던 점은 산술평균과 최빈값을 구하는 과정이었던 것 같다. 산술 평균의 경우에는 float로 바꾼 후 연산하고 cmath의 round를 이용해 값을 구했다. 최빈값 같은 경우에는 숫자가 나온 횟수를 저장하는 cnt배열을 만들어 숫자를 저장한 후 값들을 비교해 최빈값을 구했다. 소스 코드 #include #include #include #include using namespace s..
[백준] 1339번 단어 수학 C++ 문제풀이 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 맨 처음에는 자릿수마다의 알파벳을 저장해 완탐형식으로 하려 했는데 잘되지 않았다. 그래서 알파벳 별로 자릿수들의 합을 이용해 문제를 해결했다 예를 들어 1번 예시인 AAA, AAA 인 경우에는 alpha[0] = 222가 들어가는 형식이다. 아무튼 이런 방법으로 합이 큰 값들부터 정렬해서 9부터 차례로 곱해주었다. 소스코드 #include #include #include #incl..

티스토리툴바