분류 전체보기
BaekJoon 1043번: 거짓말(C++)
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이법 1) 그래프의 개념에서 접근하여, 연결된 값들을 확인하는 것이 중요하다. 2) 진실을 아는 사람이 참가한 파티에 있는 모든 사람은 주인공인 지민이가 거짓말을 하는 것을 알게 된다. 3) visited배열과 while문을 활용하여 더 이상 새로운 값으로 갱신 되지 않았을 때, 최종 결과를 구하는 것이 중요하다. (값이 바뀌는 과정에서 중간 결과를 구하려 하면 오답이 나올 수 있다.) #include #..
BaekJoon 9465번: 스티커(C++)
https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이법 1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다. 2) 점화식을 세울 때, ans 배열 규칙을 찾아야 했다. ans[0][i] = max(ans[1][i-2]+arr[0][i],ans[1][i-1]+arr[0][i]); ans[1][i] = max(ans[0][i - 2] + arr[1][i], ans[0][i - 1] + arr[1][i]); 새로 ..
BaekJoon 11660번: 구간 합 구하기 5(C++)
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이법 1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다. 2) 각 행의 합을 구해두고 이를 활용하는 방식으로 문제를 해결했다. 3) 좌표가 들어오는 경우 점화식을 활용하여, sum 값을 구해 주었다. for (int i = 0; i > x1 >> y1 >> x2..
BaekJoon 9205번: 맥주 마시면서 걸어가기(C++)
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이법 1) DFS를 이용하여 푼다면 쉽게 풀 수 있는 문제이다. 2) 절댓값의 값이 1000이하인지를 확인하여, 중간에 편의점을 들릴 수 있는지 확인하는 것이 중요하다. #include #include #include #include #include #include #include #include #include using namespace std; int t; int pantaX, pan..
BaekJoon 1706번: 크로스워드(C++)
https://www.acmicpc.net/problem/1706 1706번: 크로스워드 동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 www.acmicpc.net 풀이법 1) 문자열 처리를 위해 여러번 반복을 한다면 풀 수 있는 문제이다. 2) 배열에서 #이 나오는 경우 크기가 2이상이면 결과값의 후보인 vec 배열에 넣어준다. 3) 배열에서 #이 나오는 경우 크기가 2미만이면 기존에 string 값을 초기화 시킨다. 4) 배열에서 #이 나오지 않으면, string에 값을 추가한다. 5) 배열에서 #이 나오지 않았으며, 마지막 행 혹은 열을 탐색 시 if (..
BaekJoon 7785번: 회사에 있는 사람(C++)
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 풀이법 1) C++의 장점인 STL을 활용하였다. 2) map을 활용한다면 쉽게 풀 수 있다. 중복이 불가능하다는 점을 이용하여 map 객체에 값을 넣어둔다. 3) auto로 반복하여, 역순으로 출력하기 위해서 rbegin() 과 rend()를 사용하였다. #include #include #include #include #include #include #in..
BaekJoon 1302번: 베스트셀러
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이법 1) C++의 장점인 STL을 활용하였다. 2) map을 활용한다면 쉽게 풀 수 있다. auto로 반복하여, 최대 값을 찾고 해당하는 값을 출력하면 되는 문제이다. #include #include #include #include #include #include #include using namespace std; int n; map m; int cnt; int main() { ios..
BaekJoon 16953번: A->B(C++)
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이법 1) BFS를 활용하면 풀 수 있는 문제이다. 2) visited 배열을 사용하게 되면 memory 초과가 발생할 수 있기에 사용하지 않고 문제를 풀었다. 3) 최대 값을 1000000000로 정의하고 queue에 넣을 조건을 꼼꼼하게 설정하였다. #include #include #include #include #include #include #include #include using namespace std; #define MAXNUM 1000000000 int a, b; int ans = 0; void bfs(..
BaekJoon 10825번: 국영수(C++)
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이법 1) C++의 강점인 STL과 algorithm 헤더 내의 sort 함수를 이용하면 풀 수 있는 문제이다. 2) 조건을 compare 라는 bool type의 함수를 만들고 설정하는 과정이 가장 중요하다. 3) 팁을 적어 보자면 감소(내림차순: >) / 증가(오름차순: b.second.first) return true; else if (a.second.first == ..
BaekJoon 11123번: 양 한마리... 양 두마리...(C++)
https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 풀이법 1) BFS를 활용하여 나올 수 있는 묶음의 수를 문제이다. 2) 겹치지 않게 visit 배열을 활용하여 겹치지 않게 처리하면 풀 수 있다. 3) test case가 여러 개이므로 visited 배열을 초기화 하는 작업이 중요하다. #include #include #include #include #include #include #include #include using ..