c++/Baekjoon Online (38) 썸네일형 리스트형 백준 1946 : 신입사원 C++ https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 1. 점수가 아니라 순위를 입력 받는거니까 조심 2. 서류 순위 순으로 정렬 3. 서류 1등은 당연히 뽑는거니까 cnt = 1로 초기화하고, 루프 4.면접 점수가 서류 1등보다 높은놈을 찾아냄 -> 이제 이놈의 면접점수보다 높은놈을 이어서 찾아서 골라내면 됨 #include #include #include using namespace std; bool cmp(paira,.. 백준 1700 : 멀티탭 스케줄링 C++ https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 1. 새로운 전기용품을 충전하고 싶을때 3가지 경우가 있다 1) 이미 꽂혀 있는 경우 -> PASS 2) 꽂혀있지는 않지만, 멀티탭에 빈자리가 있음 -> 빈자리에다가 꼽는다 3) 자리가 없다 -> 이 경우가 코딩 필요 2. 현재 멀티탭에 꼽혀있는 전자제품 중에 가장 오랫동안 사용 안하는 걸 찾으면 된다. #include #include #include #include using namespa.. 백준 2579 : 계단 오르기 C++ www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 1. 우선 계단 3개 연속해서 못밟으니까 이전꺼랑 비교할때 이런 조건을 넣어야됨 max( 지금 직전+ 지금 3번째 전, 지금 2번째 전) 2. 그렇기 때문에 당연히 dp 초기화도 0 1 2 이렇게 3개 해줘야된다. #include #include using namespace std; int step[301]; int dp[301]; int main() { int x; cin >> x; for (int i = 0; i .. 백준 : 다리 만들기 2 c++ www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬들을 2번부터 시작해서 라벨링 한다!! -> bfs 이용 2. 이제 각 섬에서 다른 섬까지 연결 가능한 모든 다리 생성 후 vector에 저장 -> 길이가 2 이상이여야됨!! -> 두개의 섬 라벨과 다리 길이 value로 이루어진 struct로 관리 3. 길이 작은 순으로 sort 후 크루스칼 4. 모든 섬이 연결이 안됬으면 -1 출력 #include #include #incl.. 백준 : 기타줄 C++ www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 및 후기 1. 어려운 문제는 아닌데 이거 신경쓰는걸 까먹으면 안된다 -> 남은 낱개들을 전부 낱개로 사는거보다 그냥 세트가 더 싸면 세트로 사야됨! #include #include #include using namespace std; int main() { int n, m; int set, one; int answer = 0; int min_set = 1000; int min_one = 1000; //.. 백준 : 제곱수의 합 C++ (DP 연습!!) www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 및 후기 DP는 너무 어렵다 1. 일단 모두 1만 써서 더하는 경우는 항의 수가 자기 자신이므로 그것으로 초기화! 2. 그다음에 본인보다 작은 제곱수를 뺀 모든 경우에서의 DP값들 중 최솟값을 구하기 #include #include #include #include #include #include using namespace std; int main() { int n;.. 백준 : 퇴사 c++ www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 1. DFS로 풀었다. 경우는 두가지 1) 그날에 주어진 일을 한다! -> 일을 했으면 이게 끝나는 다음날로 이동!! 2) 그날에 주어진 날은 안하고 다음날로 넘어간다! -> 기존 day에 +1 #include #include #include #include #include using namespace std; int n; int answer = 0; vector v; void dfs(int day, int sum) { if (day > n) { answer = max(sum, answer); return; } //1번경우는 지금 날에 잡혀있.. 백준 1938 : 통나무 옮기기 c++ www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 상하좌우로 움직이는거는 기존이랑 동일하게!! 다만 방향고려해서 양 끝에도 나무 없는지 추가 확인해야된다 -> 회전을 추가! 3. 여기서 입력은 char 로 받으니까 나무 위치 비교할때 '1'인거 주의!!!!!!! ex) 구현 필요 1. wood 구조를 만든다 -> 센터 위치랑 가로 세로 여부 판단 -> way 0: 가로 1: 세로 2. 회전 가능 여부 -> 센터를 주위로 3X3 배열 구현 #include #include #include #include #include using namespace std; struct wood { pair center; int way;.. 이전 1 2 3 4 5 다음
