[백준] 4796번 캠핑 C++ 문제풀이

https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제 풀이 그리디 문제였다. 최대한 P일수를 넣은 뒤 V를 P로 나눈 나머지 값만큼을 더해주는데, V를 P로 나눈 나머지 값이 L보다 큰지 작은지만 확인한다면 어려운 문제는 아니였다. 소스 코드 #include using namespace std; int main() { int cnt = 1; while (true) { int L, P, V; cin >> L >> P >> V; if (L =..

• format_list_bulleted 알고리즘
• · 2023. 8. 17.

[백준] 1439번 뒤집기 C++ 문제풀이

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 풀이 값이 바뀌는 지점의 수를 세서 절반으로 나눠주면 값이 다 바뀌는 문제이다. 소스 코드 #include #include ; using namespace std; int main() { string s; int cnt = 0; cin >> s; for (int i = 0; i < s.size(); i++) { if (s[i] != s[i+1]) { cnt += 1; } } cout

• format_list_bulleted 알고리즘
• · 2023. 8. 16.

[백준] 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라는 ..

• format_list_bulleted 알고리즘
• · 2023. 8. 14.

[백준] 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..

• format_list_bulleted 알고리즘
• · 2023. 8. 13.

[백준] 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..

• format_list_bulleted 알고리즘
• · 2023. 8. 12.

[백준] 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 > ..

• format_list_bulleted 알고리즘
• · 2023. 8. 11.