Problem solving70 [구름톤 챌린지] 대체 경로 (C++) 문제 N개의 도시와 M개의도로가 있다. I일에는 i번 도시를 방문할 수 없다. 각 날짜별로 출발 도시부터 도착 도시까지의 경로에 포함되는 도시 개수 출력하기, 불가능한 경우에는 -1 출력 생각할 것 양방향 연결이므로 반대의 경우도 인접리스트에 추가해주었다. i일에는 큐에서 i번 도시를 꺼냈을 때 동작하지 않도록 조건을 추가하기 나머지는 그냥 날짜별로 BFS를 사용해서 최단 경로를 찾으면 된다. visited배열에 방문한 도시 개수를 기록한 뒤, 도착지에 방문하면 해당 값을 결과배열에 기록한다. 코드 #include #include #include using namespace std; int main() { int N, M, S, E; cin >> N >> M >> S >> E; vector adj(N +.. 2023. 9. 7. [구름톤 챌린지] 중첩 점 (C++) 문제 한 변의 길이가 N인 정사각형이 있다. 이 정사각형 위에 M개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세기 생각할 것 평행하지 않은 반직선만 중첩된다는 점을 이용하기. 처음에는 지나가는 위치에 모든 방향을 push_back으로 기록했다. 그랬더니 일부 테스트 케이스에서 시간 초과가 발생했다. 이를 개선하기위해 해당 위치를 지나는 점에 대해 방향의 개수만 더해주기로 했다. 마지막 테스트 케이스 하나가 틀렸다. ㅠㅠ 결과의 개수를 더할 때 오버플로우가 발생하는 문제였다. res 변수의 타입을 long long으로 바꿔주었더니 정답. 항상 주의하기! 코드 #include #include using namespace std; int dx[4] = {-1, 1, 0, 0}; int dy[4] .. 2023. 9. 6. [구름톤 챌린지] 통증 (2) (C++) 문제 통증 N과 해당 값 만큼 통증 수치를 감소시켜주는 아이템 A, B가 주어진다. 통증 수치를 0으로 줄이기 위한 아이템의 최소 사용 개수를 출력하기. 단, 통증 수치가 0보다 작아지는 아이템을 사용할 수 없다. 통증 수치를 0으로 만들 수 없는 경우 -1을 출력한다. 생각할 것 처음에는 그리디로 문제를 해결하려 했다. 하지만 예외 상황이 발생했다. 입력 10000 4 13 의 경우 그리디로 해결하면 모든 경우를 확인하지 않았기에 -1의 결과가 나오게 된다. 따라서 이 문제는 dp로 해결해야 한다. 먼저 DP배열의 크기를 총 통증 크기 + 1로 만들고, 최대값으로 초기화 한다. 각 인덱스가 통증의 크기가 되고, 배열의 값은 사용할 수 있는 최소 약의 개수이다. 그리고 1부터 N 까지 모든 경우를 탐색한.. 2023. 8. 31. [구름톤 챌린지] 발전기 (2) (C++) 문제 한변의 길이가 N인 정사각형 마을에 건물 유형 번호가 주어진다. 이때 건물 유형이 동일하면서 상하좌우 인접한 칸에 위치한 건물은 서로 전력을 공유할 수 있다. 전력을 공유할 수 있는 건물 개수가 K개 이상이면 이를 단지라고 한다. 가장 많은 단지가 있는 건물 유형을 출력하기. 생각할 것 인접한 영역을 찾는 문제는 먼저 BFS로 접근해보자. 문제의 조건을 제대로 확인하자! 영역 당 빌딩이 아무리 많더라도 단지의 개수만 추가하기 단지 개수가 동일한 영역이 여러개일 때의 단지 번호가 큰 수를 출력하기 코드 #include #include #include #include using namespace std; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; i.. 2023. 8. 31. 이전 1 2 3 4 ··· 18 다음