c++/Baekjoon Online (38) 썸네일형 리스트형 백준 18500 : 미네랄 2 c++ https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 빡구현 감 안잃기 포인트 1. 떨어져야할 클러스터 지정 다 한 다음에는, 최소 수직거리 구해서 통으로 내리기 #include #include #include #include #include #include using namespace std; int d_r[4] = { 1,-1,0,0 }; int d_c[4] = { 0,0,1,-1 }; int r, c; int n; char map[101][101]; .. 백준 1765 : 닭싸움 팀 정하기 C++ https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 풀이 1. 처음 입력을 받을때 그래프 연결하듯이 입력받는다. 2. visited를 관리하는데, 여기서 visited란 방문했다라는 표현보다는, 특정 팀에 속해있다로 이해하는게 맞다 -> 따라서 처음 루프를 확인할때 visited가 1이면 answer를 올리지 않는다. 이미 팀에 속해있고, 이 팀에 추가 멤버를 영입하는 과정이기 때문 3. 루프 1) visited가 1이면 answer는 올리지 않음 2) 내 친구면 우리팀으로 영입 -> 이미 영입 되어있어도 answer에 .. 백준 11967 : 불켜기 C++ https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 세상 비효율적으로 푼거같지만, 한방에 바로 통과해서 기분좋아서 오랫만에 풀이 정리 풀이 1. 일단 기본 map과 visited를 별개로 관리 -> 왜냐하면 visited는 불켜짐과는 상관없이 bfs에만 사용하는 용 2. map을 새로운 struct로 관리 -> 각 방에서 킬 수 있는 스위치들 vector로 관리 -> 지금 불 켜짐 여부 ( 한번.. 백준 6198 : 옥상 정원 c++ (monotone stack) https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net monotone stack이란? -> 스택 내부를 오름차순 또는 내림차순으로 유지 해주는 알고리즘 https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/ monotone stack monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다. justicehui.github.io.. 백준 2258 : 정육점 c++ https://www.acmicpc.net/problem/2258 2258번: 정육점 첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 www.acmicpc.net 고려해야될 점 1. 같은 가격인 애들이 여러개 주어졌을때를 꼭 생각해야 된다. ex) 3원짜리 고기 3g 5g vs 5원짜리 고기 10g 위의 경우의 5원짜리를 골라야 된다. 이것만 신경쓰면 쉽다 2. 가격이 싼순, 동일할때는 무게 무거운 순으로 정렬 3. 아직 합친무게가 원하는 정도가 아닌데, 동일 무게가 있으면 추가로 구매해야된다!! if (before == mea.. 백준 1461 : 도서관 C++ https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 풀이 1. 일단 당연히 음수 쪽이랑, 양수쪽이랑 분리 2. m 개씩 멀리서부터 한 그룹으로 묶기 -> 묶으면서 그 그룹의 최대값 저장해두기 3. 가장 먼 그룹 제외하고 answer += 각 그룹의 최대값 *2 4. answer += 가장 먼 그룹의 최댓값 #include #include #include using namespace std; int n, m; int answer = .. 백준 8980 : 택배 C++ https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 원래 보내는곳 순으로 정렬한 후 queue를 활용한 시뮬레이션으로 돌리려 했지만, 자꾸 틀려서 다른 분 풀이를 참고했다. 풀이 1. 우선 일거리들을 도착 빠른 순으로 정렬 2. 출발지부터 도착지 - 1 까지 잔여용량이 가장 적은 곳 찾기 3. 실을 박스의 수 정하기 -> 용량초과일 수도 있으니 4. 출발지부터 도착지 - 1 까지 실을 박수의 수만큼 잔여용량을 줄여주기 #incl.. 백준 1507 : 궁금한 민호 C++ https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. www.acmicpc.net ※ 플로이드 와샬 활용 간단 정리 -> 모든 노드끼리의 가능한 최단거리를 구하는 것임. 1) 현재 노드들 사이에 연결된 다리들을 이용해 노드간 거리 초기화 2) 기본적으로 노드를 3개 찝어서 활용 시작노드, 도착노드, 거쳐갈 노드 3) min( 시작노드 -> 도착노드, 시작노드 ->거쳐갈 노드 + 거쳐갈노드 -> 도착노드) 풀이 1. 이놈은 이미 플로이드 와샬이 적용되어 .. 이전 1 2 3 4 5 다음