좋은 수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB61620916535.256%

문제

정수 N개로 이루어진 수열 A가 있다. 이 때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력

첫째 줄에 좋은 수의 개수를 출력한다.

예제 입력 

6
1 2 3 5 7 10

예제 출력 

4

힌트












이 문제는 A + B + C = D를 찾는 문제입니다.

그렇다고 N^3을 하기에는 N이 5000까지입니다.

 

이 문제의 포인트는 2가지입니다.

 

1.  A + B = D - C 로 식을 변형한다.

2. Ai의 범위가 -10^5 ~ 10^5라는 점.


풀이 방법은 1번과 2번을 이용하면 A + B의 범위가 -2 * 10 ^5 ~ 2 * 10^5라는 것을 알 수 있습니다.저게 핵심입니다. 

저만큼의 배열을 선언해서 0부터 20만까지는 -범위 20만부터 40만까지는 + 범위입니다.

이제부터 두가지 풀이법에 대해서 설명해드리겠습니다.


1번 풀이는 i포문을 돌 때 해당 i 전까지 if(ab[data[i] - data[j] + MAX_VALUE])가 존재하는 지 검사한다.

이 말은 d - c가 존재하는지 검사합니다.

그리고 존재하면 좋은 수이므로 ret을 증가시킵니다.

 

for(int j = 0; j <= i; j++) ab[data[i] + data[j] + MAX_VALUE] = 1;

이 코드는 a+b를 존재한다고 표시해줍니다. 이 과정을 반복합니다.

 

아래의 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <string.h>
 
#define MAX_SIZE 5000
#define MAX_VALUE 200000
 
int data[MAX_SIZE];
bool ab[MAX_VALUE * 2];
 
int main()
{
 
    int n;
    scanf("%d", &n);
 
    for(int i = 0; i < n; i++) scanf("%d", data + i);
 
 
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(ab[data[i] - data[j] + MAX_VALUE])
            {
                ret++;
                break;
            }
        }
 
        for(int j = 0; j <= i; j++) ab[data[i] + data[j] + MAX_VALUE] = 1;
    }
 
    printf("%d\n", ret);
 
    return 0;
}
 
cs



아래는 2번 풀이입니다.

이 풀이는 가능한 a+b를 테이블에 다 저장합니다.

위의 풀이와 다른점은 인덱스를 저장한다는 점입니다.

a+b가 검사하는 d 이후에 만들어졌다면 사용할 수 없는 a + b이기 때문입니다.

 

if(tmp != -1 && tmp < i)를 이용해서 -1이면 a + b = d - c 를 만족하지 않으므로 좋은 수가 아니고

tmp >= i 라면 나의 인덱스보다 이후에 만들어진 수이므로 좋은 수가 아닙니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <string.h>
 
#define MAX_SIZE 5000
#define MAX_TABLE 400002
 
int n;
int data[MAX_SIZE];
int table[MAX_TABLE];
 
int main()
{
    memset(table, -1, sizeof(table));
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", data + i);
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            int sum = data[i] + data[j];
            int& tmp = table[200000 + sum];
            if(tmp == -1) tmp = i;
        }
    }
 
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            int diff = data[i] - data[j];
            int& tmp = table[200000 + diff];
            if(tmp != -1 && tmp < i)
            {
                ret++;
                break;
            }
        }
    }
 
    printf("%d\n", ret);
    return 0;
}
 
cs


'알고리즘 > 구현' 카테고리의 다른 글

[5527] 전구 장식  (0) 2017.07.05
[14499] 주사위 굴리기  (0) 2017.04.16
[3190] 뱀  (0) 2017.04.05
[1952] 달팽이2  (0) 2017.04.04
[2745] 진법 변환  (0) 2017.04.02

K번째 수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB107631821936.139%

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

출력

k번째 원소를 출력한다.

예제 입력 

3
7

예제 출력 

6

힌트
















　　　　　　　　　　　　　　　　　　　　　

너무 어려워서... 블로그 돌아다니면서 공부했습니다...

사실 아직도 정확히 이해가 안가네요...


의문점 1.. return값이 왜 left일까요...

cnt >= k 같을 경우 mid를 임시로 저장해서 끝까지 탐색한 다음 임시로 저장한 값을 출력하는 건 이해가 가는데

left가 결국 결과값이 되는 부분은 이해가 안가네요.


의문점 2.. 어째서 right에 n^2이 아닌 k를 넣는건지 잘모르겠습니다..

음.. 당연히?? k가 내가 찾는 수 보다 크기 때문에 불필요한 탐색을 줄이기 위함일까요????


세번째 의문... 이 방법을 어떻게 사람들은 생각한걸까요.. 천재일까요 T__T..머리가 너무 부럽네요..

처음에 if(cnt == k) return mid;가 왜 아닌가에 대해서 고민했는데...

i*j로 표현할 수 없는 수가 있을 수 있다고 하는데... 이것 또한 어떻게 ..생각하는 걸까요..후..



아참... 이분탐색에서 for문을 돌리는 이유는 mid값보다 작거나 같은 수를 체크하기 위함입니다.

mid / i와 n의 크기를 비교해서 작은 값을 쓰는 이유는 예를들어 n이 4라면 테이블이 아래처럼 만들어질 것입니다.


 1  2  3  4

 2  4  6  8

 3  6  9 12

 4  8 12 16


mid가 만약 6이라면 i == 1일 때 n = 4와 6 / 1 을 비교하게 됩니다.

하지만 1의 배수 중에 가장 큰 수는 4이므로 6개가 될수 없습니다.

그렇기 때문에 1의 배수 중에서 6보다 작은 수는 4개가 되겠죠.


마찬가지로 i == 2일 때 2의 배수에서도 6보다 작거나 같은 수를 찾습니다.

6/2를 하면 2, 4, 6이 포함되는 3이되겠죠.. 그렇게해서 3개


i == 3일 땐 같은 방법으로 3, 6을 포함한 2개

i == 4일 때는 4를 포함한 1개입니다.


총 카운트는 4 + 3 + 2 + 1 = 10 입니다.


이렇게 함으로써 mid보다 작은 수의 갯수를 셀 수 있습니다.



완벽히 이해는 못했지만 코드는 올리겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <algorithm>
 
int n, k;
 
int binary_search(int left, int right)
{
    if(left > right) return left;
 
    int mid = (left + right) / 2;
    int cnt = 0;
 
    for(int i = 1; i <= n; i++) cnt += n > mid / i ? mid / i : n;
 
    if(cnt < k) return binary_search(mid + 1, right);
    else return binary_search(left, mid - 1);
}
 
int main()
{
    scanf("%d %d", &n, &k);
 
    printf("%d", binary_search(1, k));
 
    return 0;
}
cs


백준에 똑같이 질문을 올렸더니 dotorya님께서 친절히 답해주셨습니다.

그림자라도 쫓을 수 있게 열심히 공부해야겠습니다.


dotorya 

1. return값이 Left가 된다는 부분 자체는 사람들마다 구현이 다르기 떄문에.. 굳이 큰 의미를 둘 이유는 없다고 생각합니다.

저도 다른 분들의 이분탐색 코드를 읽을 때는 시간이 좀 걸리는 편입니다.

다만, "cnt >= k인 가장 작은 숫자"를 탐색하고 있다는 사실만 잘 염두에 두고 코딩하신다면 문제 없을 거라고 생각합니다.


2. 생각하신 것이 맞는 것 같습니다.

추가로 N*N을 기준으로 탐색하면 long long 변수를 써야하는 귀찮음도 있을 것 같습니다.

* 여기에 더해서 드리는 말씀인데, 위 코드에서 cnt 변수에 overflow가 발생할 가능성이 없을지는 한번 확인해보시는게 좋을 것 같습니다.

아마 발생하지 않을 것 같긴 한데, 명확하게 증명해 보는게 좋겠죠..


3. 이런 방법을 처음 볼 때는 아마 누구라도 생각하기 어려울 것 같습니다.

이 문제처럼 답을 정해놓고 그 답이 가능한지 이진탐색하는 종류의 문제들을 Parametric Search라고 합니다.

사람들이 이 문제를 잘 생각하는 건, 어떻게 보면 이런 종류의 문제가 수십개씩 있었기 때문이라고도 생각되네요.

다음에 이런 문제가 나왔을 때 이 아이디어를 떠올릴 수만 있으면, 그것만으로도 잘 배우신 것이 아닐까요?

결국 그런 지식들과 응용할 수 있는 능력들이 모여서 실력이 쌓이는 거라고 생각합니다.


'알고리즘 > 이분 탐색' 카테고리의 다른 글

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19


K번째 수를 풀다가... 이분 탐색 분류가 꽤 약하다는 것을 다시 한번 느껴서...

푼 것도 다시 풀어볼 예정입니다...

커플 만들기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB129934023227.008%

문제

여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.

당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.

입력

첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.

출력

첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.

예제 입력 

2 1
10 20
15

예제 출력 

5

힌트



















풀다가 머리에 쥐나서.. 섬광탄 맞은 것처럼 띵~~~하게 하는 난이도네요..(라헬이..생각나고..)

처음에 dp인줄도 모르고 그리디로 풀어서 엄청 틀렸네요..



이 문제를 풀 때 꿀팁은 항상 여자 혹은 남자의 데이터 수가 많다고 생각하고 푸는 것입니다.

저는 무조건 여자가 많게 만들어서 풀었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
    scanf("%d %d", &m, &g);
 
    for(int i = 0; i < m; i++) scanf("%d", data1 + i);
    for(int j = 0; j < g; j++) scanf("%d", data2 + j);
 
    if(m > g)
    {
        swap(data1, data2);
        swap(m, g);
    }
 
    sort(data1, data1 + m);
    sort(data2, data2 + g);
cs


인풋과 정렬까지 하는 부분입니다.

만약 m(남자)가 크면 g(여자)와 swap을 해서 데이터를 바꿔줍니다.


남자의 데이터(1, 2, 3, 4), 여자의 데이터(a,b,c,d,e,f,g)라고 가정하겠습니다.


1

2

3

4


1가 선택할 수 있는 여자는 a,b,c,d입니다.


a

b

c

d

e

f

g


2가 선택할 수 있는 여자는 b,c,d,e입니다.

a

b

c

d

e

f

g


3이 선택할 수 있는 여자는 c,d,e,f입니다.


a

b

c

d

e

f

g


4가 선택할 수 있는 여자는 d,e,f,g입니다.


a

b

c

d

e

f

g



dp는 2차원으로 정의합니다.


dp[남자][여자] = 남자가 여자를 선택했을 때 까지 궁합의 합의 최솟값입니다.


예를 들어 1번 남자가 b번 여자를 선택한다면 2번 남자는 c,d,e만 선택할 수 있습니다.


dp[1][a]는 (1번 남자 성격) - (a번 여자 성격)의 절대값입니다.


그리고 dp[1][b]는 (1번 남자 성격) - (b번 여자 성격)의 절대값과 dp[1][a] 둘 중에 작은 값을 선택해서 저장합니다.

이 작업을 dp[1][d]까지 반복합니다.


점화식으로 표현하면 이 부분은 i == 0일 때 입니다.

1
2
3
4
5
6
7
8
    for(int i = 0; i < m; i++)
    {
        if(i == 0)
        {
            dp[0][0] = abs(data1[0] - data2[0]);
 
            for(int j = 1; j < g - (m - i - 1); j++) dp[i][j] = min(dp[i][j - 1], abs(data1[0] - data2[j]));
        }
cs


이후에 2-b를 연결한다고 생각하면 2-b의 절대값에 1-a를 더합니다. 그리고 dp[2][b]에 그 값을 저장합니다.


2-c를 연결한다고 생각하면 2-c의 절대값을 구하여서 dp[1][b]까지의 최솟값에 더하고 dp[2][b]값과 비교하여 작은 값을 저장합니다.

이 부분이 핵심이며.. 이 작업을 반복하면 정답을 구할 수 있습니다.


1
2
3
4
5
6
7
8
        else
        {
            for(int j = i; j < g - (m - i - 1); j++)
            {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + abs(data1[i] - data2[j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + abs(data1[i] - data2[j]), dp[i][j - 1]);
            }
        }
cs



아래는 풀 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
 
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define MAX_SIZE 1010
#define MAX_MOVE 31
 
using namespace std;
 
typedef pair<int, int> p;
 
int data1[MAX_SIZE];
int data2[MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
int m, g;
 
int abs(int a)
{
    if(a>=0) return a;
    else return -a;
}
 
int main()
{
    scanf("%d %d", &m, &g);
 
    for(int i = 0; i < m; i++) scanf("%d", data1 + i);
    for(int j = 0; j < g; j++) scanf("%d", data2 + j);
 
    if(m > g)
    {
        swap(data1, data2);
        swap(m, g);
    }
 
    sort(data1, data1 + m);
    sort(data2, data2 + g);
 
    for(int i = 0; i < m; i++)
    {
        if(i == 0)
        {
            dp[0][0] = abs(data1[0] - data2[0]);
 
            for(int j = 1; j < g - (m - i - 1); j++) dp[i][j] = min(dp[i][j - 1], abs(data1[0] - data2[j]));
        }
        else
        {
            for(int j = i; j < g - (m - i - 1); j++)
            {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + abs(data1[i] - data2[j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + abs(data1[i] - data2[j]), dp[i][j - 1]);
            }
        }
    }
 
    printf("%d\n", dp[m - 1][g - 1]);
 
    return 0;
} 
 
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19
[2293] 동전 1  (4) 2017.04.19
[2240] 자두나무  (0) 2017.04.05

자두나무 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB230498566940.993%

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

예제 입력 

7 2
2
1
1
2
2
1
1

예제 출력 

6

힌트















DP는 식을 정의를 하는 것이 가장 중요하다고 생각합니다.

문제가 '매 초마다 두 개의 나무에서 떨어지는 자두를 최대로 먹어라' 입니다.


매번 움직여서 받을 수 있다면 떨어지는 자두 수가 최대이겠지만..

안타깝게도 움직임이 제한되어있습니다. (W)


그래서 저는 X초에 Y번 움직이고 먹은 최대의 자두 수라고 정의를 했습니다.

변수가 두개이니 2차원 DP가 될 것입니다.


1
2
3
4
#define MAX_SIZE 1010
#define MAX_MOVE 31
int data[MAX_SIZE];
int dp[MAX_SIZE][MAX_MOVE];
cs


이 문제를 푸신 분들을 보면 3차원 DP로 정의하는 경우가 있는데..

그 정의는 X초에 Y번 움직이고 Z의 위치에 있을 때 먹은 최대의 자두 수 입니다.

물론 이렇게 풀어도 되지만..


저는 Y번 움직일 때 사람(자두)의 위치를 알 수 있습니다.

1번 나무에서 시작하므로 한번 움직였다면 2번 나무

두번 움직였다면 1번 나무

세번 움직였다면 2번 나무

.

.

.


n번 움직였다면 n % 2가 짝수일 때 1번 나무, 홀수일 때 2번 나무입니다.

이 문제의 핵심이죠~


아래의 코드는 점화식입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
    for(int i = 1; i <= T; i++)
    {
        if(data[i] == 1) dp[i][0] = dp[i - 1][0] + 1;
        else dp[i][0] = dp[i - 1][0];
 
        for(int  j = 1; j <= i && j <= W; j++)
        {
            if(data[i] == 1 && j % 2 == 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else if(data[i] == 2 && j % 2 == 1) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
 
            ret = max(ret, dp[i][j]);
        }
    }
cs


i초에 떨어지는 자두가 1이고 움직인 수가 짝수라면
혹은 i초에 떨어지는 자두가 2이고 움직인 수가 홀수라면..
혹은 i초에 떨어지는 자두가 1인데 나는 2에 있거나.. 2인데 나는 1에 있거나 하면 i - 1초에서의 최대 자두 수를 넣으면 됩니다.


아래는 문제의 풀코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
 
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define MAX_SIZE 1010
#define MAX_MOVE 31
 
using namespace std;
 
typedef pair<int, int> p;
 
int data[MAX_SIZE];
int dp[MAX_SIZE][MAX_MOVE];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int main()
{
    int T, W;
    scanf("%d %d", &T, &W);
 
    for(int i = 1; i <= T; i++) scanf("%d", data + i);
 
    int ret = 0;
 
    for(int i = 1; i <= T; i++)
    {
        if(data[i] == 1) dp[i][0] = dp[i - 1][0] + 1;
        else dp[i][0] = dp[i - 1][0];
 
        for(int  j = 1; j <= i && j <= W; j++)
        {
            if(data[i] == 1 && j % 2 == 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else if(data[i] == 2 && j % 2 == 1) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
 
            ret = max(ret, dp[i][j]);
        }
    }
 
    printf("%d\n", ret);
    return 0;
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19
[2293] 동전 1  (4) 2017.04.19
[1727] 커플 만들기  (0) 2017.04.05

뱀 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB127022916817.573%

문제

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딫히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그대로 OK
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.(즉, 몸길이는 변하지 않는다.) 

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초(seconds)후에 끝나는지 계산하라.

입력

첫째줄에 N이 주어진다. ( 2 ≤ N ≤ 100 )

다음줄에 사과의 개수 K가 주어진다.( 0 ≤ K ≤ 100 )

그리고 K개의 줄에는 사과의 위치가 주어지는데, 첫번째 숫자는 행(row), 두번째 숫자는 열(column) 위치를 의미한다. 맨위 맨좌측(1행 1열) 에는 사과가 없다.

그리고 뱀의 방향변환 개수 L 이 주어진다. ( 1 ≤ L ≤ 100 )

그리고 L개의 줄에는 뱀의 방향변환 정보가 주어지는데,  숫자 X와 문자 C로 이루어져 있다. X초 후에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 방향을 변경 한다는 뜻이다. X는 10,000이하의 양의 정수이다.

출력

문제의 정답,  즉 초(seconds) 를 첫째줄에 출력하라.

예제 입력 

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 

9

힌트















맵을 배열로 선언할 수 있다는게 난이도가 높진 않았습니다.

알고리즘 분류는 구현보다는 시물레이션에 가까운 것 같네요..


사과의 위치는 맵에 2로 표현했고, 턴하는 위치는 v벡터에 sec와 꺽는 방향을 페어로 넣었습니다.


이 문제의 핵심은 뱀의 흔적을 저장하는 것입니다.


저는 간단하게 벡터에 저장했고, 맵이 0이라면

snake벡터의 맨 앞의 좌표에 해당하는 곳을 0으로 바꿔주고 맨 앞 벡터를 삭제했습니다.


아래의 코드입니다.


1
2
3
4
5
6
7
8
9
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) break; // 맵 벗어나는지 검사
 
        //맵검사
        if(map[nx][ny] == 1) break;
        else if(map[nx][ny] == 0)
        {
            map[snake[0].first][snake[0].second] = 0;
            snake.erase(snake.begin());
        }
cs


그리고 2를 만나던 0을 만나던 머리 부분은 1로 갱신하고 백터의 맨뒤에 뱀의 머리 좌표를 삽입합니다.


1
2
3
4
5
//스네이크 머리 갱신 및 맵 갱신
        x = nx;
        y = ny;
        map[x][y] = 1;
        snake.push_back(mp(x, y));
cs




아래는 문제의 풀 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
#define mp make_pair
 
using namespace std;
 
typedef pair<int, int> p;
 
int N, K, L;
int map[MAX_SIZE][MAX_SIZE]; // 사과는 2, 뱀은 1, 맵은 0
vector<p> v; //sec, turn
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
//오른쪽 : 위 -> 오, 아래 -> 왼, 오 -> 아, 왼 -> 위
//왼쪽 : 위 -> 왼, 아래 -> 오른, 오 -> 위, 왼 -> 아
 
//r : 0 -> 3, 1 -> 2, 3 -> 1, 2 -> 0
//l : 0 -> 2, 1 -> 3, 3 -> 0, 2 -> 1
 
int turn(int now, int next)
{
    if(next == 0) // 왼쪽
    {
        if(now == 0 || now == 1) return (now + 2) % 4;
        else return 3 - now;
    }
    else // 오른쪽
    {
        if(now == 0 || now == 1) return 3 - now;
        else return (now + 2) % 4;
    }
}
 
 
void input()
{
    scanf("%d %d", &N, &K);
 
    for(int i = 0; i < K; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        map[x - 1][y - 1] = 2;
    }
 
    scanf("%d", &L);
 
    for(int i = 0; i < L; i++)
    {
        int s;
        char c;
 
        scanf("%d %c", &s, &c);
 
        int d;
        if(c == 'L') d = 0; //왼
        else d = 1; //오른쪽
 
        v.push_back(mp(s, d));
    }
}
 
void process()
{
    vector<p> snake;
 
    int x = 0, y = 0; // 머리 위치
 
    int d = 3;
    int sec = 0;
 
    int vi = 0;//시간 벡터 인덱스
    bool v_flag = 0;//벡터가 끝나면 1이됨
 
    map[x][y] = 1;
    snake.push_back(mp(x, y));
 
    while(1)
    {
        if(!v_flag && sec == v[vi].first)
        {
            d = turn(d, v[vi++].second);
            if(vi == v.size()) v_flag = 1;
        }
 
        //다음 좌표
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) break; // 맵 벗어나는지 검사
 
        //맵검사
        if(map[nx][ny] == 1) break;
        else if(map[nx][ny] == 0)
        {
            map[snake[0].first][snake[0].second] = 0;
            snake.erase(snake.begin());
        }
 
        //스네이크 머리 갱신 및 맵 갱신
        x = nx;
        y = ny;
        map[x][y] = 1;
        snake.push_back(mp(x, y));
 
        sec++;
    }
 
    printf("%d\n", sec + 1);
}
 
 
int main()
{
    input();
    process();
 
    return 0;
}
cs


'알고리즘 > 구현' 카테고리의 다른 글

[14499] 주사위 굴리기  (0) 2017.04.16
[5624] 좋은 수  (0) 2017.04.06
[1952] 달팽이2  (0) 2017.04.04
[2745] 진법 변환  (0) 2017.04.02
[3460] 이진수  (0) 2017.04.02

달팽이2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB47826021656.397%

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

ㅇ  
   
   
   
   

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

ㅇ→↘
↗↘↓
↑↓↓
↑끝↓
↖←↙

위의 표는 선을 그려 나간 모양을 나타낸 것이다. (선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2≤M, N≤100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

예제 입력 

5 3

예제 출력 

5

힌트













예전에는 굉장히 어렵게 생각해서 실패했던 문제인데...

지금 푸니까 왜 이렇게 쉬울까요..


방향이 꺾이는 경우는 딱 두가지입니다.

1. 맵 밖으로 나간다.

2. 방문했던 곳이다.


예전엔 2번이 어려웠는데... 그냥 맵을 만들어서 방문표시하면 끝인데.. 왜어렵게 생각했을까요...

와일문 탈출조건은 

만약 방향을 꺾어서 이동했음에도 불구하고 방문한 곳이라면 모든 맵을 다 방문한 것입니다!!

그러므로 탈출하고 마지막에 꺾인 부분은 제외해야하므로 1을 뺴준것이 정답입니다.!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
 
 
bool visit[MAX_SIZE][MAX_SIZE];
int m, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
//3 -> 1, 1 -> 2, 2 -> 0, 0 -> 3
//오 -> 아, 아 -> 왼, 왼 -> 위 , 위 -> 오
 
int set_direct(int d)
{
    if(d == 3 || d == 2) return (d + 2) % 4;
    else return 3 - d;
}
 
 
int main()
{
 
    scanf("%d %d", &m, &n);
 
    int x=0, y=0;
    int d = 3;
    int ret = 0;
 
    while(1)
    {
        if(visit[x][y] == 1) break;
 
        visit[x][y] = 1;
 
        int nx = x + dx[d];
        int ny = y + dy[d];
 
 
        if(visit[nx][ny] == 1 || nx < 0 || ny < 0 || nx >= m || ny >= n)
        {
            d = set_direct(d);
            nx = x + dx[d];
            ny = y + dy[d];
            ret++;
        }
 
        x = nx;
        y = ny;
    }
 
    printf("%d\n", ret - 1);
 
    return 0;
}
cs


'알고리즘 > 구현' 카테고리의 다른 글

[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05
[2745] 진법 변환  (0) 2017.04.02
[3460] 이진수  (0) 2017.04.02
[2399] 거리의 차이  (2) 2017.04.02

환승 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB95221115624.111%

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최소값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력 

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 

4

힌트















N을 입력받았다면 하이퍼튜브의 좌표를 N + 1부터 N + M + 1까지라고 생각했습니다.

하이퍼튜브와 일반 정점의 차이는 cost입니다.

하이퍼튜브로 가는 비용은 0이고 다른 정점으로 가는 비용은 1입니다.


그리고 다익스트라를 이용해서 N까지의 최소비용을 구하면 간단하게 해결할 수 있습니다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
 
#include <algorithm>
#include <string.h>
 
#include <stack>
#include <vector>
#include <queue>
 
#define MAX_SIZE 102000
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define INF 0x7fffffff
 
using namespace std;
typedef pair<int, int> p;
 
vector<int> v[MAX_SIZE];
 
int n, k, m;
int dist[MAX_SIZE];
bool visit[MAX_SIZE];
int pos;
 
 
 
void dijkstra()
{
    for(int i = 2; i < pos; i++) dist[i] = INF;
 
    priority_queue<p> pq; // - 로 값을 넣자
    pq.push(mp(-1, 1));
 
    while(!pq.empty())
    {
        p pop_data = pq.top();
        pq.pop();
 
        int from = pop_data.second;
        int cnt = -pop_data.first;
 
        if(visit[from]) continue;
        visit[from] = 1;
 
        for(int i = 0; i < v[from].size(); i++)
        {
            int to = v[from][i];
            int add = 1;
 
            if(to > n) add--; // 하이퍼 튜브면 -를 해서 cost를 0로 만든다.
 
            if(dist[to] > cnt + add)
            {
                dist[to] = cnt + add;
                pq.push(mp(-dist[to], to));
            }
        }
    }
}
 
 
int main()
{
    scanf("%d %d %d", &n, &k, &m);
 
 
    pos = n + 1; // 하이퍼튜브 좌표
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < k; j++)
        {
            int to;
            scanf("%d", &to);
            v[pos].push_back(to);
            v[to].push_back(pos);
        }
 
        pos++;
    }
 
    dijkstra();
    printf("%d\n", dist[n] == INF ? -1 : dist[n]);
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[9009] 피보나치  (0) 2017.04.04
[9328] 열쇠  (0) 2017.04.02

+ Recent posts

티스토리툴바