문제 농부 존은 그의 들판에 N(1≤N≤10,000)개의 건초 더미를 놓으려 한다. 들판은 1*1 크기의 사각형으로 구성된 100*100 크기이고, 건초 더미들은 각각 1*1 크기의 사각형 한 칸을 차지한다. (한 칸에 두 개의 건초 더미가 놓이는 일은 없다) 농부 존은 건초 더미로 연결된 다양한 형태의 하나의 큰 영역이 생기는 것을 알았다. 즉, 건초 더미들 모두 인접한 (동서남북으로 한 칸) 곳에 다른 건초 더미가 있다. 한 건초 더미에서 출발해서 다른 모든 건초 더미에 도달할 수 있다. 건초 더미로 연결된 영역은 “구멍”을 포함할수있다. 구멍은 건초 더미로 완전히 둘러싸인 빈 영역이다. 농부 존이 건초 베일에 의해 형성되는 영역의 둘레를 계산하는 것을 도와주시오. “구멍”은 둘레에 영향을 주지 않는..
문제 문제 바로가기> 정올 1169번: 주사위 던지기1 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 각각 중복순열, 중복조합, 순열을 구현하는 문제이다. 오랜만에 풀어보니 약간 헷갈.. 렸다 ㅎㅎ 순열: 서로 다른 n개 중에서 r개를 선택하여 일렬로 세우는 경우 중복순열: 서로 다른 n개 중에서 중복을 허락하고 r개를 일렬로 나열하는 수 조합: 서로 다른 n개 중에서 r개를 선택하여 그룹을 만드는 경우 (순서 상관 x) 중복조합: 서로 다른 n개 중에서 순서를 생각하지 않고 중복을 허락하여 r개를 선택하는 경우 #include #define MAX 7 using namespace std; int N, M; int seq[MAX]; bool visited[MAX]; void inp..
문제 문제 바로가기> 정올 2097번: 지하철 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 다익스트라를 이용하여 최소 시간을 구해주었다. 최단 경로의 경우, (최단 경로일 때만 경로 업데이트가 일어나므로) 경로가 업데이트 될 때 이전 역을 저장하고 역추적하는 방식으로 쉽게 구할 수 있다. #include #include #include #define MAX 105 #define INF 1000000001 #define pii pair using namespace std; int N, M; int cost[MAX]; // cost[k]: 1번역에서 k 역까지 가는데 걸리는 시간 int stopover[MAX]; // 경유지 저장 vector v[MAX]; void input(){ ..
문제 문제 바로가기> 정올 1141번: 불쾌한 날 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 N이 최대 80,000이므로 각 소에 대해서 이중 for문을 돌면서 확인할 경우 시간초과가 발생한다. 내가 볼 수 있는 소의 수를 세는 것이 아니라, 나를 볼 수 있는 소의 수를 센다면, O(N)으로 문제를 해결할 수 있다. 다음과 같이 스택 안에 나(H[i])를 볼 수 있는 소들만 들어 있도록 유지하면 된다. (1번 소가 3번 소를 볼 수 있고, 3번 소가 4번 소를 볼 수있으면, 1번 소는 4번 소를 볼 수있다.) #include #include #define MAX 80001 using namespace std; int N; int H[MAX]; void input(){ cin >..
문제 개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연 잎 들을 이용해서 이리저리 뛰어 놀고 있다. 개구리가 뛰는 장면을 보던 철수는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다. 1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다. 2. 개구리는 오른쪽으로만 뛴다. 3. 개구리는 두 번만 뛴다. 4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다. 허나, 연 잎 들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 철수는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 철수를 위해 프로그램을 짜주자. 첫 번째 줄에는 연 잎의 수 N(3 ≤ N ≤ 1,000..
문제 문제 바로가기> 정올 1985번: 분수 정렬 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 1 * 1/2과 2/4처럼 값이 겹치는 경우 분모가 작은 1/2을 선택 (분모가 작으면 분자도 작다) 조합 가능한 모든 분수를 생성해주고, 분수값(오름차순) 과 분모값(오름차순)을 기준으로 정렬해준다. 만약 분수값이 이전 분수값과 같다면 continue 해주면 된다. 분모의 범위를 2부터, 분자의 범위를 1부터 한 것은 0과 1이 되는 값은 어차피 0/1과 1/1이 출력될 것이기 때문이다. 100000 을 곱해준 후 나눈 값을 저장한 것은 소수가 아닌 정수 형태로 저장하기 위함이다. 1.0을 곱해주고 double로 저장해서 계산해도 된다. #include #include #include..