2792번: 보석 상자 (acmicpc.net) 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 난이도 : 실버2 해결 과정 : 이분 탐색으로 푸는 문제 였습니다. 나눠줄 때 한 색깔종류로만 나눠줘야 하기 때문에 각 색상의 개수 / 질투심 값과 나눴을 때 나머지가 나온다면 +1 해서 각각 더해진 cnt 값이 학생의 수와 같으면 right 값을 줄여주는 식으로 구현 하였습니다. 맨 첨에 left값을 0으로했다가 100퍼에서 틀렸다고 나오길래 1로 고쳐줬습니다. 코드 : #include #include #inclu..
Algorithm/Solution
14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 와.. 그냥 빡구현으로 풀었슴... ㅋ ㅋ ㅋ 푼다음에 다른 사람꺼 풀이 보니까 dy dx 배열 선언해서 4방향으로 돌수 있게 반복문으로 처리한거같았는데 나는 그 방향 바뀔 때 dy dx가 규칙성 있게 바뀔 거라는 건 예상이 가지만 수식이 도저히 생각이 안나서.... 그냥 동서남북 조건 나눠서 일일히 x랑 y값 선언해주면서 했음.. 위에 chk함수는 청소하고자 하는 (r,c)가..
15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 각 집마다의 치킨거리를 구해 마을의 총 치킨거리가 최소가 되도록하는 문제입니다. n이 50이므로 최대 집 개수+치킨집개수은 250이 됩니다. 따라서 집개수와 치킨집 개수가 반반이라고 했을 때 최대 125*125 = 15625 번 연산을 하므로 제한시간이 1초라서 완탐으로 풀 수 있는 문제 였습니다. 완전탐색문제가 되면 복잡할거없이 치킨집을 조합으로 m개 고른다..
2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 난이도 : 골드3 풀이 과정 : 위상정렬 문제로 사이클 여부 판별 + 중복간선 제거 를 해결해야되는 문제였습니다. 저는 맨처음엔 벡터로 하려다가 set자료형을 이용하여(중복을 허용하지 않음) set배열로 입력을 받았습니다. 만약에 중복된 간선이 나오면 삽입을 해도 set배열의 크기가 같으므로 만약 삽입을 했는데도 전에랑 크기가 같으면 진입차수를 저장하는 배열은 업데이트를 하지 않게 해주었습니다..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 최근에 코테를 몇번 참가해보면서 구현을 정확하고 빠르게 푸는 것의 중요성을 깨달았다. 이 문제는 구현+bfs인데, 백준에서 bfs문제중 바이러스 문제가 있어서 그거 먼저 풀면 도움이 될듯하다. n과 m이 최대 8까지기 때문에 완탐! 으로 가능하다 왜냐면 0이나올수 있는 곳에 벽 3개를 두는 것이기 때문에 최대 64C3 번 연산 이기 때문 관건은 벽 3개를 두는 방법을 어떻게 ..
2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 난이도 : 골드5 풀이방법: 이분탐색 문제인데, 내가 구한 방식은 일단 좌표를 오름차순으로 정렬을하고, 첫번째 인덱스부터 시작해서 반복문을 돌려 차이가 mid이상이면 두 점 차이가 가능하다는 의미에서 chk=true로 해주었고, 공유기 개수를 +1 해준다. 그다음 mid이상이나오는 인덱스부터 다시시작해서 다음번째 그다다다음번째가 mid이상인지 계속 체크해서 공유..
14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 난이도 : 골드5 풀이과정 : 완전 탐색 문제이다. 모든 경우의 수.. 회전.. 대칭 에 대한 모든 경우의 수를 따져주면된다. 기존 좌표가 (x,y) 라 할때 나올수 있는 회전, 대칭에 대한 경우의 수는 8개 (x,y), (x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x), (-y,-x) 다음과 같다..!!! 중딩때 배우던가... 이거 rx배열은 부호곱해줘야되서 선언해줬다. 이 걸 ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 난이도 : 골드 4 풀이과정 : 다익스트라를 이용한 문제 2차원 배열에서 다익스트라 알고리즘을 활용하면 되는 문제였다. 도둑루피 값은 2차원 배열에 저장하고, 우선순위 큐는 다중 페어를 이용하여 pair (pair 형태로 넣어주도록 했다. 가중치 dist 배열은 2차원 벡터 형태로 선언하였다. 다익스트라를 안다면 2차원 형태를 어떻게 구현하느냐가 주요 문제였음 코드 : #incl..
11779번: 최소비용 구하기 2 (acmicpc.net) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 난이도 : 골드 3 풀이 방법 : 다익스트라를 이용하는 문제 경로를 출력하는 것이 관건이었다... 경로를 출력하는 방법을 도시 개수만큼 배열(route)을 선언해 주고 다익스트라에서 dist(비용) 이 업데이트 될 때, 업데이트 되는 next인덱스에 전 노드 here 값을 저장 시켜준다. 그러면 route배열의 각 인덱스에는 인덱스 전의 노드의 인덱스 가 저장 되어 있는 것..
