[실버 1] 1743 음식물 피하기 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net [알고리즘 분류] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 2 초 128 MB 15782 7371 5838 46.775% 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한..
말랑말랑
[실버 3] 11659 : 구간 합 구하기 4 [알고리즘 분류] 누적 합 1 초 256 MB 63347 26884 20513 40.662% 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N [접근법] 일단 입력받는 정수 개수가 최대 10만 개, 그리고 합을 구해야 하는 연산..
[실버 3] 3273 : 두 수의 합 [알고리즘 분류] 정렬, 투 포인터 1 초 128 MB 31308 11118 8429 35.184% 문제 n개의 서로 다른 양의 정수 a1, a2,..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj) 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. [접근법] 처음에는 정렬을 쓰지 않..
문제를 풀기 원한다면 여기로. 막 어려운 문제는 아니었다. 사실 문제를 제대로 파악하고 푼 건 아니고 이게 되네 정도? 깔끔한 풀이는 아닌 거 같다. 분명 더 좋은 방법이 있을거 같음. --- 11/29 수정 --- 더 좋은 방법을 찾았다!! 사실 더 좋은 방법인지는 모르겠고 확실한 건 타일 하나가 줄었다 ㅋㅋㅋ.. [32/50]
문제를 풀고 싶다면 여기로. 빙글빙글 돌아가는 미로 모양의 맵이다. 가장 마지막 부분의 빨간색 발판이 연달아 나오는 지점에서 조건을 잘 설정하면 된다. [31/50]
문제를 풀고 싶다면 여기로. 이름답게 해골 모양의 맵이다. 각 색깔의 바닥을 지날 때마다 방향을 꺾으면 되는 쉬운 문제지만, 한 가지 다른 점은 중앙의 초록색 점이다. 결국은 저 초록색 점을 두 번 지나야 하는데, 지날 때마다 꺾는 방향이 다르기 때문. 첫 번째 방문시 초록색 발판에서 오른쪽으로 꺾어야 하지만, 두 번째 방문할 때는 초록색 발판에서 왼쪽으로 꺾어야 한다. [30/50]
문제를 풀고 싶다면 여기로. 보자마자 어지러운 모양을 하고 있다. 더군다나 우주선 모양이 옆을 보고 있어서 더 어렵게 느껴지는 것 같다. 실제로도 상당히 까다로운 문제였는데, 이때까지 푼 robozzle 난이도가 평균 2점대였다면 이 문제는 3.5였다. 문제가 상당히 어렵다. F1은 제일 아래쪽에서 옆으로 한 칸씩 이동하며 F2를 호출한다. F2는 빨간색 발판이 나올때 까지 위로 오르다가 빨간색이 나오면 꺾고 아래로 내려간다. [29/50]
문제를 풀고 싶다면 여기로. 맵이 커서 처음에 어렵게 보일 수 있다. 하지만 코너에만 초록색이 존재하는 규칙이 있기 때문에 쉽게 풀 수 있다. 한 가지 주의할 점은 길 중간에 빨간색 발판이 등장하면 다음 초록색 발판 때 꺾이는 방향이 반대가 되는 것. F1과 F2 타일 배치가 깔끔하다. 만족 ㅎㅎ [28/50]
문제를 풀고 싶다면 여기로. 어디서 많이 본 모양인데, 바로 419번 문제를 많이 닮았다. 똑같이 풀 수 있을 줄 알았으나 생각보다 복잡하다. 초록색에서 꺾는 것 까지는 같지만, 다시 돌아올 때도 초록색이기에 수정이 필요하다. F1은 초록색을 만나기 전까지 직진하면서 F2를 호출한다. F2가 실행되면 우주선은 별을 먹고 다시 방향 전환을 하고 다시 F1을 반복하여 초록색 발판이 없다면 쭉 직진하여 빨간색 발판에 도착하게 된다. [27 / 50]
문제를 풀고 싶다면 여기로. 이것도 발판 색 바꾸는 타일이 있는데 못 보고 한참 헤매다가 풀었다.. 발판 색 안바꾸고는 도저히 못 풀겠어서 고민하다가 색 바꾸는 타일을 보고 바로 풀었다. 시간은 많이 끌었는데, 생각보다 쉬운듯! 초록색 발판만 파란색으로 바꾸는 게 포인트. [26/50]
