BOJ[백준] - 1012 - 유기농배추

Posted by ceyx
2018. 5. 19. 16:56 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1012

 

 

DFS 또는 BFS로 풀면 될 것 같습니다.

BFS를 쓰면 방문여부만으로도 해결이 되는 문제입니다. 그런걸보면 flood fill 느낌이 나네요..

 

 

1. DFS 입니다.

 

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
#include <stdio.h>
char land[52][52];
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
 
void dfs(int x, int y)
{
  if (!land[x][y]) return;
  land[x][y] = 0;
  for (int i=0; i<4; i++)
    dfs(x+dx[i], y+dy[i]);
}
int main(void)
{
  int T;
  scanf("%d",&T);
  while (T--)
  {
    int m,n,k;
    scanf("%d %d %d"&m, &n, &k);    
    while(k--)
    {
      int x, y;
      scanf("%d %d"&x, &y);
      land[y+1][x+1= 1;
    }
    int Needed = 0;
    for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
        if (land[i][j])
        {
          dfs(i,j);
          Needed++;
        }
    printf("%d\n", Needed);
  }
  return 0;
}
cs

 

 

 

2.  BFS 입니다.

 

가독성을 위해 아래처럼 코드를 짰지만, 사실 enqueue나 dequeue는 따로 함수로 둘 필요없죠 ㅋ

 

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
#include <cstdio>
 
#define MAX_NUM        (52)
 
typedef struct { int x; int y; } PAIR;
int head, tail, Needed;
int dx[4= { 0,1,0,-1 }, dy[4= { 1,0,-1,0 };
PAIR queue[(MAX_NUM * MAX_NUM)];
char land[MAX_NUM][MAX_NUM];
 
void enqueue(PAIR t)
{
    queue[head++= t;
    head = head % MAX_NUM;
}
 
PAIR dequeue()
{
    PAIR t = queue[tail++];
    tail = tail % MAX_NUM;
    return t;
}
 
void BFS(PAIR p)
{
    int tx, ty;
    enqueue(p);
    while (head != tail)
    {
        PAIR p2 = dequeue();
        tx = p2.x, ty = p2.y;
        for (int i = 0; i<4; i++)
            if(land[tx + dx[i]][ty + dy[i]])
                land[tx + dx[i]][ty + dy[i]] = 0, enqueue({ tx + dx[i], ty + dy[i] });
    }
}
 
int main()
{
    int t;
    scanf("%d"&t);
    while (t--)
    {
        int m, n, k;
        scanf("%d %d %d"&m, &n, &k);
        while(k--)
        {
            int x, y;
            scanf("%d %d"&x, &y);
            land[y+1][x+1= 1;
        }
        head = tail = Needed = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (land[i][j])
                {
                    land[i][j] = 0;
                    BFS({ i, j });
                    Needed++;
                }
            }
        }
        printf("%d\n", Needed);
    }
    return 0;
}
cs
이 댓글을 비밀 댓글로

변수, 상수, 정수, 실수, 진수, 데이타 단위

Posted by ceyx
2017. 9. 29. 16:51 C 언어/강의

c언어를 사용하는데 있어서 기본적으로 알아야 한다는 느낌으로 알고 넘어가죠

쉽게 이해하고 넘어가야 하기 때문에 1의보수, 2의보수, 지수 표현법 이런 것들은 나중에 보는게 좋겠습니다.



....작성중



'C 언어 > 강의' 카테고리의 다른 글

변수, 상수, 정수, 실수, 진수, 데이타 단위  (0) 2017.09.29
C언어 강의 목차  (0) 2017.06.24
이 댓글을 비밀 댓글로

BOJ[백준] - 2262 - 토너먼트 만들기

Posted by ceyx
2017. 7. 30. 19:20 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/2262

 

 

이 문제는 i ~ j  라는 range가 있다면 그 중간에 k를 두고 i~k 과 k+1 ~ j 로 나누어 최소값이나 최대값을 구하는 류의..

문제들에 속하네요..

 

 

비슷한 문제로는 아래와 같은 것들이 있습니다.. 매우 비슷하네요 ㅎㅎ

BOJ[백준] - 11066 - 파일합치기

BOJ[백준] - 11049 - 행렬 곱셈 순서

 

 

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
#include <cstdio>
#define MXN    ( 257 )
#define abs(a,b)  ((a)>(b) ? (a-b):(b-a))
#define min(a,b)  ((a)>(b) ? (b):(a))
 
int d[MXN][MXN], w[MXN][MXN], a[MXN], n;
int f(int x, int y)
{
   if(x == y)
      return 0;
   if(x + 1 == y)
      return (abs(a[x], a[y]));
   if(d[x][y])
      return d[x][y];
   int &ans = d[x][y];
   ans = abs(a[x], w[x + 1][y]) + f(x + 1, y);
   for(int i = x+1; i < y; i++)
   {
      ans = min(ans, abs(w[x][i], w[i+1][y]) + f(x, i) + f(i+1, y));
   }
   return ans;
}
int main()
{
   scanf("%d"&n);
   for(int i = 1; i <= n; i++)
      scanf("%d"&a[i]);
 
   for(int i = 1; i <= n; i++)
   {
      w[i][i] = a[i];
      for(int j = i + 1; j <= n; j++)
         w[i][j] = min(w[i][j - 1], a[j]);
   }
   printf("%d", f(1, n));
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 13458 - 시험 감독

Posted by ceyx
2017. 7. 18. 21:44 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/13458

 

 

 

 

쉽습니다..

 

부감독관의 수를 세는 것만 약간 유의해 주세요 ^^;

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#define RoundupMultiple(a, x)    ((a+(x-1))/x)
 
int a[1000001];
int main()
{
   int n, b, c;
   scanf("%d"&n);
   for(int i = 1; i <= n; i++)
      scanf("%d"&a[i]);
   scanf("%d %d"&b, &c);
 
   long long sum = 0;
   for(int i = 1; i <= n; i++)
   {
      a[i] -= b, sum++;
      if(a[i] > 0)
         sum += RoundupMultiple(a[i], c);
   }
   printf("%lld", sum);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1912 - 연속합

Posted by ceyx
2017. 7. 15. 01:48 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1912

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
 
const int MXN = 100000;
int a[MXN+1], dp[MXN+1];
int main()
{
   int n;
   scanf("%d"&n);
   for (int i = 1; i <= n; i++)
   {
      scanf("%d"&a[i]);
      if(a[i] <= dp[i - 1+ a[i])
         dp[i] = dp[i - 1+ a[i];
      else
         dp[i] = a[i];
   }
   int max = -1001;
   for (int i = 1; i <= n; i++)
      max = (max < dp[i] ? dp[i] : max);
 
   printf("%d", max);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1890 - 점프

Posted by ceyx
2017. 7. 15. 01:47 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1890

 

 

 

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 <cstdio>
 
long long dp[111][111];
int a[101][101];
int main()
{
   int N, i, j;
   scanf("%d"&N);
   for(i = 1; i <= N; i++)
      for(j = 1; j <= N; j++)
         scanf("%d"&a[i][j]);
 
   dp[1][1= 1;
   for(i = 1; i <= N; i++)
   {
      for(j = 1; j <= N; j++)
      {
         if(a[i][j] == 0)
            continue;
         dp[i + a[i][j]][j] += dp[i][j];
         dp[i][j + a[i][j]] += dp[i][j];
      }
   }
   printf("%lld", dp[N][N]);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1720 - 타일 코드

Posted by ceyx
2017. 7. 15. 01:46 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1720

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
 
int dp[31], dp2[31];
int main()
{
   int N, i, tmp;
   scanf("%d"&N);
 
   dp[1= 1, dp[2= 3;
   for(i = 3; i <= N; i++)
      dp[i] = dp[i - 2* 2 + dp[i - 1];
 
   dp2[1= 1, dp2[2= 3;
   for(i = 3; i <= N; i++)
   {
      if(i & 1)
         tmp = dp[(i - 1/ 2];
      else
         tmp = dp[i / 2+ (2 * dp[(i - 2/ 2]);
      dp2[i] = (dp[i] + tmp) / 2;
   }
   printf("%d", dp2[N]);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1699 - 제곱수의 합

Posted by ceyx
2017. 7. 15. 01:45 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1699

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
 
int dp[100001];
int main()
{
   int n;
   scanf("%d"&n);
   for (int i = 1; i <= n; i++) {
      dp[i] = i;
      for (int j = 1; j*<= i; j++) {
         if (dp[i] > dp[i - j*j] + 1) {
            dp[i] = dp[i - j*j] + 1;
         }
      }
   }
   printf("%d", dp[n]);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1520 - 내리막 길

Posted by ceyx
2017. 7. 15. 01:44 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1520

 

 

 

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
#include <stdio.h>
 
int dp[501][501], a[501][501], N, M, i, j;
int nx[] = { 1,-1,0,0 }, ny[] = { 0,0,1,-1 };
 
int solve(int x, int y)
{
   int ret = 0;
   if(x == 0 || y == 0)
      return 0;
   if(x == N && y == M)
      return 1;
   if(dp[x][y] != -1)
      return dp[x][y];
   for(int i = 0; i < 4; i++)
      if(a[x][y] > a[x + nx[i]][y + ny[i]])
         ret += solve(x + nx[i], y + ny[i]);
   return dp[x][y] = ret;
}
 
int main()
{   
   scanf("%d %d"&N, &M);
   for(i = 1; i <= N; i++)
      for(j = 1; j <= M; j++)
         scanf("%d"&a[i][j]),dp[i][j]=-1;
 
   printf("%d", solve(1,1));
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1509 - 팰린드롬 분할

Posted by ceyx
2017. 7. 15. 01:43 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1509

 

 

 

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 <cstring>
 
char chk[2501][2501];
int d[2501];
char s[2502];
 
int main() 
{
   int n, i, j, k;
   scanf("%s", s + 1);
   n = strlen(s + 1);
   for(i = 1; i <= n; i++)
      chk[i][i] = 1;
 
   for(i = 1; i <= n - 1; i++)
      if(s[i] == s[i + 1])
         chk[i][i + 1= 1;
 
   for(k = 2; k<n; k++)
   {
      for(i = 1; i <= n - k; i++)
      {
         j = i + k;
         chk[i][j] = (s[i] == s[j] && chk[i + 1][j - 1]);
      }
   }
 
   d[0= 0;
   for(i = 1; i <= n; i++)
   {
      d[i] = -1;
      for(j = 1; j <= i; j++)
      {
         if(chk[j][i])
         {
            if(d[i] == -1 || d[i] > d[j - 1+ 1)
            {
               d[i] = d[j - 1+ 1;
            }
         }
      }
   }
   printf("%d\n", d[n]);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1495 - 기타리스트

Posted by ceyx
2017. 7. 15. 01:42 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1495

 

 

 

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
#include <stdio.h>
 
int a[101];
char dp[101][1001];
 
int main()
{
   int N, S, M, i, j, ans = -1;
   scanf("%d %d %d"&N, &S, &M);
 
   for(i = 1; i <= N; i++)
      scanf("%d"&a[i]);
 
   // assign digit 1 for the all of possible cases 
   dp[0][S] = 1;
   for(i = 1; i <= N; i++)
   {
      for(j = 0; j <= M; j++)
      {
         if(dp[i - 1][j])
         {
            if(j - a[i] >= 0)
               dp[i][j - a[i]] = 1;
            if(j + a[i] <= M)
               dp[i][j + a[i]] = 1;
         }
      }
   }
   for(i = 0; i <= M; i++)
      if(dp[N][i])
         ans = i;
 
   printf("%d", ans);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1463 - 1로 만들기

Posted by ceyx
2017. 7. 15. 01:41 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1463

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
 
#define MIN(a,b)  ((a)<(b) ? (a):(b))
int dp[1000001];
int main()
{
   int x;
   scanf("%d"&x);
   dp[1= 0;
   for(int i = 2; i <= x; i++)
   {
      dp[i] = dp[i - 1];
      if(i % 3 == 0)
         dp[i] = MIN(dp[i], dp[i / 3]);
      if(i % 2 == 0)
         dp[i] = MIN(dp[i], dp[i / 2]);
      dp[i]++;
   }
   printf("%d", dp[x]);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1328 - 고층 빌딩

Posted by ceyx
2017. 7. 15. 01:40 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1328

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
long long dp[101][101][101];
int main()
{
   int N, L, R, i, j, k;
   scanf("%d %d %d"&N, &L, &R);
 
   dp[1][1][1= 1LL;
   for(i = 2; i <= N; i++)
      for(j = 1; j <= L; j++)
         for(k = 1; k <= R; k++)
            if(i >= j && i >= k)
            {
               dp[i][j][k] += dp[i - 1][j - 1][k];
               dp[i][j][k] += dp[i - 1][j][k - 1];
               dp[i][j][k] += (dp[i - 1][j][k] * (i - 2));
               dp[i][j][k] %= 1000000007;
            }
 
   printf("%lld", dp[N][L][R]);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1126 - 같은탑

Posted by ceyx
2017. 7. 15. 01:36 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1126

 

 

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
#include <cstdio>
#define MAX(a,b)  ((a)>(b) ? (a):(b))
const int inf = 10000000;
int a[50], dp[50][250001], n;
 
int go(int k, int diff)
{
   if(diff > 250000)
      return -inf;
   if(k == n)
   {
      if(diff == 0)
         return 0;
      else
         return -inf;
   }
   if(dp[k][diff] != -1)
      return dp[k][diff];
   dp[k][diff] = go(k + 1, diff);
   dp[k][diff] = MAX(dp[k][diff], go(k + 1, diff + a[k]));
   if(a[k] > diff)
      dp[k][diff] = MAX(dp[k][diff], diff + go(k + 1, a[k] - diff));
   else
      dp[k][diff] = MAX(dp[k][diff], a[k] + go(k + 1, diff - a[k]));
   return dp[k][diff];
}
 
int main()
{
   scanf("%d"&n);
   for(int i = 0; i<n; i++)
      scanf("%d"&a[i]);
   for(int i = 0; i < 50; i++)
      for(int j = 0; j < 250001; j++)
         dp[i][j] = -1;
   
   int ans = go(00);
   printf("%d", (ans ? ans : -1));
   return 0;
}
cs
이 댓글을 비밀 댓글로

Minimum Spanning tree (최소신장트리)

Posted by ceyx
2017. 7. 15. 01:25 Algorithm/Graph

설명 쓸 예정..

 

 

 

 

 

 

 

관련 문제 리스트

 

BOJ[백준] - 1647 - 도시 분할 계획

BOJ[백준] - 1922 - 네트워크 연결

BOJ[백준] - 4386 - 별자리 만들기

BOJ[백준] - 6497 - 전력난

이 댓글을 비밀 댓글로

Shortest Path (최단거리) 에 관하여..

Posted by ceyx
2017. 7. 15. 01:18 Algorithm/Graph

설명 쓸 예정입니다..

 

 

 

 

 

 

 

 

관련 문제 리스트

 

BOJ[백준] - 1753 - 최단경로

BOJ[백준] - 2610 - 회의준비

이 댓글을 비밀 댓글로

What is DP ? 다이나믹 프로그래밍이란 ?

Posted by ceyx
2017. 7. 15. 01:15 Algorithm/Dynamic Programming

설명 쓸 예정입니다...

 

 

관련 문제 리스트

 

BOJ[백준] - 1126 - 같은탑 

BOJ[백준] - 1328 - 고층 빌딩

BOJ[백준] - 1463 - 1로 만들기

BOJ[백준] - 1495 - 기타리스트

BOJ[백준] - 1520 - 내리막 길

BOJ[백준] - 1509 - 팰린드롬 분할

BOJ[백준] - 1699 - 제곱수의 합

BOJ[백준] - 1720 - 타일 코드

BOJ[백준] - 1890 - 점프

BOJ[백준] - 1912 - 연속합

BOJ[백준] - 2262 - 토너먼트 만들기

BOJ[백준] - 8984 - 막대기

 

'Algorithm > Dynamic Programming' 카테고리의 다른 글

What is DP ? 다이나믹 프로그래밍이란 ?  (0) 2017.07.15
이 댓글을 비밀 댓글로

DFS(깊이우선탐색) and BFS(너비우선탐색)

Posted by ceyx
2017. 7. 15. 01:11 Algorithm/Graph

알고리즘 설명 쓸 예정..

 

 

 

 

 

관련 문제 리스트

 

백문[BOJ] - 1012 - 유기농배추

백준[BOJ] - 1260 - DFS와 BFS

백준[BOJ] - 2589 - 보물섬

백준[BOJ] - 10026 - 적록색약

이 댓글을 비밀 댓글로

BOJ[백준] - 6497 - 전력난

Posted by ceyx
2017. 7. 14. 01:51 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/6497

 

네네.. 그렇습니다. 역시.. MST 문제네요~ Kruskal (크루스칼) 알고리즘 사용했습니다.

 

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
// Kruskal algorithm
#include <cstdio>
 
typedef struct edge
{
   int a, b, w;
} EDGE;
 
const int MXN = 200000;
EDGE e[MXN + 3], tmp[MXN + 3];
int rep[MXN + 1]; // parent vertex info
 
int f(int x)   // return representative vertex's index
{
   if(x == rep[x])
      return x;
   else
      return (rep[x] = f(rep[x]));
}
void mergesort(int l, int r)
{
   if(l < r)
   {
      int m = (l + r) / 2;
      mergesort(l, m);
      mergesort(m + 1, r);
      // p1 [l ~ m], p2 [m+1 ~ r], p3 [l ~ r]
      int p1 = l, p2 = m + 1, p3 = l;
      while(p1 <= m && p2 <= r)
      {
         if(e[p1].w < e[p2].w) // judgement factor is weight(cost)
            tmp[p3++= e[p1++];
         else
            tmp[p3++= e[p2++];
      }
      while(p1 <= m) tmp[p3++= e[p1++];
      while(p2 <= r) tmp[p3++= e[p2++];
      for(int i = l; i <= r; i++)
         e[i] = tmp[i];
   }
}
 
int main()
{
   int n, m, total;
   while(scanf("%d %d"&n, &m))
   {
      if(n == 0 && m == 0)
         break;
 
      total = 0;
      for(int i = 0; i < m; i++)
      {
         scanf("%d %d %d"&e[i].a, &e[i].b, &e[i].w);
         rep[i] = i;
         total += e[i].w;
      } 
      mergesort(0, m-1);
 
      // scan the all of original edge data,
      // BUT if the # of edges will be ( n-1 ), that's the Minimum Spanning Tree
      //                                        because all the vertices are connected.
      int cnt = 0, minw = 0;
      for(int i = 0; i < m; i++)
      {
         int r1 = f(e[i].a), r2 = f(e[i].b);
         if(r1 == r2)   // a and b are in the same union
            continue;
 
         rep[r2] = r1;
         minw += e[i].w;
         cnt++;
         if(cnt == n - 1)
            break;
      }
      printf("%d\n", (total - minw));
   }
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 4386 - 별자리 만들기

Posted by ceyx
2017. 7. 14. 01:49 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/4386

 

MST(최소신장트리) 문제네요~ Kruskal (크루스칼) 알고리즘 사용했습니다.

(1) 다만, 이 문제는 직접 edge를 만들어 줘야 하는 번거로움이 있네요.. 피타고라스의 정리를 사용해야 했습니다. ㅎㅎ

 

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
// Kruskal algorithm
#include <cstdio>
#include <math.h>
#include <algorithm>
using namespace std;
 
typedef struct star
{
   double x, y;
} STAR;
typedef struct edge
{
   int a, b;
   double w;
} EDGE;
 
const int MXN = 100, MXM = 10000;
EDGE e[MXM + 1], tmp[MXM + 1];
int rep[MXN + 1]; // parent vertex info
STAR st[101];
int f(int x)   // return representative vertex's index
{
   if(x == rep[x])
      return x;
   else
      return (rep[x] = f(rep[x]));
}
void mergesort(int l, int r)
{
   if(l < r)
   {
      int m = (l + r) / 2;
      mergesort(l, m);
      mergesort(m + 1, r);
      // p1 [l ~ m], p2 [m+1 ~ r], p3 [l ~ r]
      int p1 = l, p2 = m + 1, p3 = l;
      while(p1 <= m && p2 <= r)
      {
         if(e[p1].w < e[p2].w) // judgement factor is weight(cost)
            tmp[p3++= e[p1++];
         else
            tmp[p3++= e[p2++];
      }
      while(p1 <= m) tmp[p3++= e[p1++];
      while(p2 <= r) tmp[p3++= e[p2++];
      for(int i = l; i <= r; i++)
         e[i] = tmp[i];
   }
}
 
int main()
{
   int n;
   scanf("%d"&n);
   for(int i = 0; i < n; i++)
      scanf("%lf %lf"&st[i].x, &st[i].y);
 
   int ne = 0// number of edges
   for(int i = 0; i < n; i++)
   {
      for(int j = i + 1; j < n; j++)
      {
         e[ne].a = i;
         e[ne].b = j;
         e[ne].w = sqrt(pow(abs(st[i].x - st[j].x), 2+ pow(abs(st[i].y - st[j].y), 2));
         ne++;
      }
   }
 
   for(int i = 0; i <= ne; i++)
      rep[i] = i;
 
   mergesort(0, ne - 1);
 
   // scan the all of original edge data,
   // BUT if the # of edges will be ( n-1 ), that's the Minimum Spanning Tree
   //                                        because all the vertices are connected.
   int cnt = 0;
   double ans = 0;
   for(int i = 0; i < ne; i++)
   {
      int r1 = f(e[i].a), r2 = f(e[i].b);
      if(r1 == r2)   // a and b are in the same union
         continue;
 
      rep[r2] = r1;
      ans += e[i].w;
      cnt++;
      if(cnt == n - 1)
         break;
   }
   printf("%.2lf", ans);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1922 - 네트워크 연결

Posted by ceyx
2017. 7. 14. 01:47 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1922

 

MST(최소신장트리) 문제입니다. Kruskal (크루스칼) 알고리즘 사용했습니다.

 

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
// Kruskal algorithm
#include <cstdio>
 
typedef struct edge
{
   int a, b, w;
} EDGE;
 
const int MXN = 1000, MXM = 100000;
EDGE e[MXM+1], tmp[MXM+1];
int rep[MXN+1]; // parent vertex info
 
int f(int x)   // return representative vertex's index
{
   if(x == rep[x])
      return x;
   else
      return (rep[x] = f(rep[x]));
}
void mergesort(int l, int r)
{
   if(l < r)
   {
      int m = (l + r) / 2;
      mergesort(l, m);
      mergesort(m + 1, r);
      // p1 [l ~ m], p2 [m+1 ~ r], p3 [l ~ r]
      int p1 = l, p2 = m + 1, p3 = l;
      while(p1 <= m && p2 <= r)
      {
         if(e[p1].w < e[p2].w) // judgement factor is weight(cost)
            tmp[p3++= e[p1++];
         else
            tmp[p3++= e[p2++];
      }
      while(p1 <= m) tmp[p3++= e[p1++];
      while(p2 <= r) tmp[p3++= e[p2++];
      for(int i = l; i <= r; i++)
         e[i] = tmp[i];
   }
}
 
int main()
{
   int n, m;
   scanf("%d %d"&n, &m);
   for(int i = 0; i < m; i++)
      scanf("%d %d %d"&e[i].a, &e[i].b, &e[i].w);
   for(int i = 0; i <= n; i++)
      rep[i] = i;
 
   mergesort(0, m-1);
   
   // scan the all of original edge data,
   // BUT if the # of edges will be ( n-1 ), that's the Minimum Spanning Tree
   //                                        because all the vertices are connected.
   int cnt = 0;
   long long ans = 0;
   for(int i = 0; i < m; i++)
   {
      int r1 = f(e[i].a), r2 = f(e[i].b);
      if(r1 == r2)   // a and b are in the same union
         continue;
      
      rep[r2] = r1;
      ans += e[i].w;
      cnt++;
      if(cnt == n - 1)
         break;
   }
   printf("%lld", ans);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1647 - 도시 분할 계획

Posted by ceyx
2017. 7. 14. 01:42 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1647

 

MST(최소신장트리) 문제의 기본이네요~!  Kruskal (크루스칼) 알고리즘입니다.

 

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
// Kruskal algorithm
#include <cstdio>
 
typedef struct edge
{
   int a, b, w;
} EDGE;
 
const int MXN = 100000, MXM = 1000000;
EDGE e[MXM + 1], tmp[MXM + 1];
int rep[MXN + 1]; // parent vertex info
 
int f(int x)   // return representative vertex's index
{
   if(x == rep[x])
      return x;
   else
      return (rep[x] = f(rep[x]));
}
void mergesort(int l, int r)
{
   if(l < r)
   {
      int m = (l + r) / 2;
      mergesort(l, m);
      mergesort(m + 1, r);
      // p1 [l ~ m], p2 [m+1 ~ r], p3 [l ~ r]
      int p1 = l, p2 = m + 1, p3 = l;
      while(p1 <= m && p2 <= r)
      {
         if(e[p1].w < e[p2].w) // judgement factor is weight(cost)
            tmp[p3++= e[p1++];
         else
            tmp[p3++= e[p2++];
      }
      while(p1 <= m) tmp[p3++= e[p1++];
      while(p2 <= r) tmp[p3++= e[p2++];
      for(int i = l; i <= r; i++)
         e[i] = tmp[i];
   }
}
 
int main()
{
   int n, m;
   scanf("%d %d"&n, &m);
   for(int i = 0; i < m; i++)
      scanf("%d %d %d"&e[i].a, &e[i].b, &e[i].w);
   for(int i = 0; i <= n; i++)
      rep[i] = i;
 
   mergesort(0, m-1);
 
   // scan the all of original edge data,
   // BUT if the # of edges will be ( n-2 ), that's the 2 Minimum Spanning Trees.
   int cnt = 0;
   long long ans = 0;
   for(int i = 0; i < m; i++)
   {
      int r1 = f(e[i].a), r2 = f(e[i].b);
      if(r1 == r2)   // a and b are in the same union
         continue;
 
      rep[r2] = r1;
      ans += e[i].w;
      cnt++;
      if(cnt == n - 2)
         break;
   }
   printf("%lld", ans);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 2610 - 회의준비

Posted by ceyx
2017. 7. 14. 01:40 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/2610

 

아시다시피 최단거리 알고리즘은, 대표적으로 3가지 정도 있습니다. 그런데 고맙게도 이 문제는 N이 굉장히 작은 수(100이하)네요 ^^;

Floyd-Warshall (플로이드-와셜) 알고리즘을 사용했습니다.

 

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
// Floyd-Warshall algorithm
#include <cstdio>
#include <algorithm>
using namespace std;
 
#define MIN(a,b)  ((a)<(b)? (a):(b))
#define INF       ( 1000000000 )
 
int dist[101][101], maxi[101], rep[100], gn, flag[101];
 
int main()
{
   int N, M, i, j ,k;
   scanf("%d %d"&N, &M);
   
   // initialization
   for(i = 1; i <= N; i++)
      for(j = 1; j <= N; j++)
         dist[i][j] = (i == j ? 0 : INF);
 
   while(M--)
   {
      scanf("%d %d"&i, &j);
      dist[i][j] = dist[j][i] = 1;
   }
 
   // shortest distance ( Floyd-Warshall algorithm )
   for(k = 1; k <= N; k++)
      for(i = 1; i <= N; i++)
         for(j = 1; j <= N; j++)
            dist[i][j] = MIN(dist[i][j], dist[i][k] + dist[k][j]);
   
   for(i = 1; i <= N; i++)
      for(j = 1; j <= N; j++)
         if(dist[i][j] < INF && dist[i][j] > maxi[i])
            maxi[i] = dist[i][j];
 
   for(i = 1; i <= N; i++)
   {
      if(!flag[i])
      {
         int t = i;
         for(int j = i; j <= N; j++)
         {
            if(dist[i][j] < INF)
            {
               flag[j] = 1;
               if(maxi[t] > maxi[j])
                  t = j;
            }
         }
         rep[gn++= t;
      }
   }
   sort(rep, rep + gn);
   printf("%d", gn);
   for(int i = 0; i < gn; i++)
      printf("\n%d", rep[i]);
 
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 10026 - 적록색약

Posted by ceyx
2017. 7. 14. 01:35 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/10026

 

보물섬문제와 매우 흡사합니다 ㅎㅎ 

다만, 색약 아닌 사람과 색약인 사람, 이렇게 2경우만 계산해보면 되겠네요

 

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
#include <stdio.h>
 
#define MAXNUM 100
int a[(MAXNUM * MAXNUM) + 1][4], a_blind[(MAXNUM * MAXNUM) + 1][4], q[(MAXNUM * MAXNUM) + 1], N;
char rgb[(MAXNUM * MAXNUM) + 1];
 
int BFS(int arr[][4])
{
   int head = 0, tail = 0, group = 0;
   char chk[(MAXNUM * MAXNUM) + 1= {0, };  // init visit info.
   for(int i = 1; i <= (N*N); i++)
   {
      if(!chk[i])
      {
         q[head++= i;
         while(head != tail)
         {
            int tmp = q[tail++];
            for(int j = 0; j < 4; j++)
            {
               if(arr[tmp][j] && !chk[arr[tmp][j]])
               {
                  q[head++= arr[tmp][j];
                  chk[arr[tmp][j]] = 1;
               }
            }
         }
         group++;
      }
   }
   return group;
}
int main()
{
   int i, j, tmp;
   scanf("%d"&N);
   for(i = 0; i < N; i++)
   {
      scanf("\n");
      for(j = 1; j <= N; j++)
      {
         tmp = (i*N) + j;
         scanf("%c"&rgb[tmp]);
         // [x][0] = x's east,[x][1] = x's west,[x][2] = x's south,[x][3] = x's north
         if((j - 1) % N != 0)
         {
            if(rgb[tmp - 1== rgb[tmp])
            {
               a_blind[tmp][1= a[tmp][1= tmp - 1;
               a_blind[tmp - 1][0= a[tmp - 1][0= tmp;
            }
            else if((rgb[tmp - 1== 'R' && rgb[tmp] == 'G'|| (rgb[tmp - 1== 'G' && rgb[tmp] == 'R'))
            {
               a_blind[tmp][1= tmp - 1;
               a_blind[tmp - 1][0= tmp;
            }
         }
         if(i > 0)
         {
            if(rgb[tmp - N] == rgb[tmp])
            {
               a_blind[tmp][3= a[tmp][3= tmp - N;
               a_blind[tmp - N][2= a[tmp - N][2= tmp;
            }
            else if((rgb[tmp - N] == 'R' && rgb[tmp] == 'G'|| (rgb[tmp - N] == 'G' && rgb[tmp] == 'R'))
            {
               a_blind[tmp][3= tmp - N;
               a_blind[tmp - N][2= tmp;
            }
         }
      }
   }
   printf("%d %d", BFS(a), BFS(a_blind));
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 2589 - 보물섬

Posted by ceyx
2017. 7. 14. 01:33 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/2589

 

(1) 모든 칸 사이의 이동길이(1, 가중치없음)가 같고 거리를 구하는 것이기 때문에 전형적인 BFS를 사용해야 하는 문제입니다.

(2) 모든 육지정점에서 출발하여 서로 가장 먼 곳(보물이 있는곳)을 찾아봅시다.

  loop 돌 때마다(새로운 육지에서 출발할 때마다), visited 여부를 초기화 해야 한다는 것이 유의할 점이겠네요~

 

STL 안쓰고 푼 문제라서.. 소스가 좀 길어요^^;;

 

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
#include <stdio.h>
 
#define MAXNUM 50
int a[(MAXNUM * MAXNUM) + 1][4], q[(MAXNUM * MAXNUM) + 1];
char chk[(MAXNUM * MAXNUM) + 1], dist[(MAXNUM * MAXNUM) + 1];
 
int main()
{
   int N, M, head=0, tail=0, i, j, tmp, max = 0;
   char c;
   scanf("%d %d"&N, &M);
   for(i = 0; i < N; i++)
   {
      scanf("\n");
      for(j = 1; j <= M; j++)
      {
         scanf("%c"&c);
         tmp = (i*M) + j;
         chk[tmp] = dist[tmp] = (c != 'L');
         if(!chk[tmp])
         {
            // [x][0] = x's east,[x][1] = x's west,[x][2] = x's south,[x][3] = x's north
            if((j - 1) % M != 0 && !chk[tmp - 1])
            {
               a[tmp][1= tmp - 1;
               a[tmp - 1][0= tmp;
            }
            if(i > 0 && !chk[tmp - M])
            {
               a[tmp][3= tmp - M;
               a[tmp - M][2= tmp;
            }
         }
      }
   }
 
   for(i = 1; i <= (N*M); i++)
   {
      if(!dist[i])
      {
         //BFS
         q[head++= i;
         dist[i] = 1;
         while(head != tail)
         {
            tmp = q[tail++];
            for(j = 0; j < 4; j++)
            {
               if(a[tmp][j] && !dist[a[tmp][j]])
               {
                  q[head++= a[tmp][j];
                  dist[a[tmp][j]] = dist[tmp] + 1;
               }
            }
         }
      }
      if(max < dist[tmp])
         max = dist[tmp] - 1;
      head = tail = 0// avoid runtime error
 
      for(j = 1; j <= (N*M); j++)
         dist[j] = chk[j];
   } 
   printf("%d", max);
   return 0;
}
cs

 

이 댓글을 비밀 댓글로

BOJ[백준] - 1260 - DFS와 BFS

Posted by ceyx
2017. 7. 14. 01:28 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1260

 

DFS와 BFS를 연습할 수 있는 기본이 되는 문제입니다.

 

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
#include <cstdio>
 
#define MAXNUM 1001
 
int N, M, head, tail;
int queue[MAXNUM];
int graph[MAXNUM][MAXNUM];
int isVisited[MAXNUM];
 
int isEmpty()
{
   return (head == tail);
}
 
void enqueue(int n)
{
   queue[head++= n;
   head = head % MAXNUM;
}
 
int dequeue()
{
   int ret;
   if(isEmpty())
      return -1;
   else
   {
      ret = queue[tail++];
      tail = tail % MAXNUM;
      return ret;
   }
}
 
void DFS(int v)
{
   int i;
   if(isVisited[v])
      return;
   printf("%d ", v);
   isVisited[v] = true;
 
   for(i = 1; i <= N; i++)
      if(graph[v][i])
         DFS(i);
}
 
void BFS(int v)
{
   int i, val;
   enqueue(v);
   isVisited[v] = true;
   
   while(!isEmpty())
   {
      val = dequeue();
      printf("%d ", val);
 
      for(i = 1; i <= N; i++)
      {
         if(graph[val][i] && !isVisited[i])
         {
            enqueue(i);
            isVisited[i] = true;
         }
      }
   }
}
 
int main()
{
   int V, v1, v2, i;
   scanf("%d %d %d"&N, &M, &V);
   while(M--)
   {
      scanf("%d %d"&v1, &v2);
      graph[v1][v2] = graph[v2][v1] = 1;  // adjacent matrix
   }
 
   DFS(V);
 
   // initialization
   for(i = 1; i <= N; i++)
      isVisited[i] = false;
 
   printf("\n");
   BFS(V);
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1753 - 최단경로

Posted by ceyx
2017. 7. 14. 01:16 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/1753

 

SPFA (Shortest Path Faster Algorithm)을 사용했습니다.  큐 사이즈가 쓸데 없이 큽니다 ㅎㅎ.. STL 을 사용하는게 좋겠네요~!

 

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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MXV = 20005, inf = 1000000000;
vector<pair<intint>> ed[MXV];
int dist[MXV], q[300000], h, t;
bool inQ[MXV];
int main()
{
   int nv, ne, s;
   scanf("%d %d %d"&nv, &ne, &s);
   for (int i = 1; i <= ne; i++)
   {
      int u, v, w;
      scanf("%d %d %d"&u, &v, &w);
      ed[u].push_back({ v, w });
   }
   for (int i = 1; i <= nv; i++)
      dist[i] = inf, inQ[i] = false;
 
   // BFS
   dist[s] = 0;
   q[t++= s, inQ[s] = true;
   while (h != t)
   {
      int a = q[h++];
      inQ[a] = false;
      for (auto it : ed[a])
      {
         if (dist[it.first] > (dist[a] + it.second))
         {
            dist[it.first] = dist[a] + it.second;
            if (!inQ[it.first])
            {
               q[t++= it.first;
               inQ[it.first] = true;
            }
         }
      }
   }
   for (int i = 1; i <= nv; i++)
      if (dist[i] >= inf)
         puts("INF");
      else
         printf("%d\n", dist[i]);
 
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 8984 - 막대기

Posted by ceyx
2017. 7. 13. 18:56 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/8984

 

문제의 예제 입력을 가지고 봅시다..

(1) stick 배열에 넣고, 정렬   {<1,0>, <2,5>, <4,5>, <4,8>, <6,0>, <6,5>, <8,8>}

(2) t만 넣은 vector = tv 와 d만 넣은 vector dv 에서 unique()와 erase() 를 이용하여 중복되는 값을 전부 제거하면 다음과 같습니다.

tv { 1, 2, 4, 6, 8 }  -> 그림으로 보면 윗 줄엔  5개 점,  아래쪽 줄에는.. 3개점만 있는거죠..!

dv { 0, 5, 8 }

(3) DP 배열을 준비해 봅니다.

(4) 이제 준비는 끝났습니다. T_dp[x] 는 tv의 x번째 항목에 해당하는 좌표의 점으로 끝나는 zig-zag의 MAX길이가 되네요..

결국 결과는 아래와 같네요 !  D_dp[1] 은 dv의 1번 idx, 즉, d가 5번 좌표인 점으로 끝나는 지그재그의 길이는 a, b, e를 선택했을 때니까 17이 맞습니다.

T_dp[0] = 4, [1] = 6, [2] = 10, [3] = 13, [4] = 20

D_dp[0] = 9, [1] = 17, [2] = 17

 

답은 zig-zag의 최대값이므로 20입니다.

 

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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MXN = 100001;
int N, L;
long long T_dp[MXN];
long long D_dp[MXN];
pair<int,int> stick[MXN];
vector<int> tv, dv;
 
int main()
{
   scanf("%d%d"&N, &L);
   for(int i = 0; i<N; i++)
   {
      scanf("%d%d"&stick[i].first, &stick[i].second);  // <t,d> pair
      tv.push_back(stick[i].first);
      dv.push_back(stick[i].second);
   }
   sort(stick, stick + N);
   sort(tv.begin(), tv.end());
   sort(dv.begin(), dv.end());
   // eliminate the duplicated values & reduce the size of each vector
   tv.erase( unique(tv.begin(), tv.end()), tv.end() );
   dv.erase( unique(dv.begin(), dv.end()), dv.end() );
   long long ans = 0;
   for(int i = 0; i < N; i++)
   {
      int t_idx = lower_bound(tv.begin(), tv.end(), stick[i].first) - tv.begin();
      int d_idx = lower_bound(dv.begin(), dv.end(), stick[i].second) - dv.begin();
      int len = L + (abs(stick[i].first - stick[i].second));
      long long t = T_dp[t_idx], d = D_dp[d_idx];
      // (T_dp, D_dp) array has the maximum length of zig-zag pattern ending with the point(t & d vector). 
      T_dp[t_idx] = max(t, d + len);
      D_dp[d_idx] = max(d, t + len);
      ans = max(T_dp[t_idx], max(ans, D_dp[d_idx]));
   }
   printf("%lld",ans);
   return 0;
}
 
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 1316 - 그룹 단어 체커

Posted by ceyx
2017. 7. 13. 02:45 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1316

 

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 <cstdio>
 
int main()
{
   int n, ng = 0;
   scanf("%d\n"&n);
   while(n--)
   {
      char s[101= { 0, };
      int chk[27= { 0, };
      scanf("%s", s);
      int prev=-1, curr, i;
      for(i = 0; s[i] != '\0'; i++)
      {
         curr = s[i] - 'a';
         if(prev != curr && chk[curr] != 0)
            break;
         chk[curr]++;
         prev = curr;
      }
      if (s[i]=='\0')
         ng++;
   }
   printf("%d", ng);
   return 0;
}
cs
이 댓글을 비밀 댓글로

BOJ[백준] - 6223 - Cow Sorting

Posted by ceyx
2017. 7. 13. 01:37 Algorithm 문제풀이/BOJ [백준] 문제풀이

https://www.acmicpc.net/problem/6223

 

이 문제는 2569번 - 짐정리 문제와 똑같죠?

다만 #include <algorithm> 을 썼습니다..

 

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
// Cow Sorting
 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MXN = 10000;
pair<int,int> a[MXN + 1];
char chk[MXN + 1];
 
int main()
{
   int n;
   scanf("%d"&n);
   // a[].first = data, a[].second = index
   for (int i = 0; i < n; i++)
   {
      scanf("%d"&a[i].first);
      a[i].second = i;
   }
   sort(a, a + n);
 
   long long ans = 0;
   for (int i = 0; i < n; i++)
   {
      if (chk[i])
         continue;
      int cycle = 0;
      // loop 1 cycle, cycle = the # of vertices in a cycle
      for (int j = i; !chk[j]; j = a[j].second)
      {
         cycle++;
         ans += a[j].first;
         chk[j]++;
      }
      // case 1 : check only non-sorted cyclic vertices
      //          4 2 1 3 -> check (1,3,4) -> (1+3) + (1+4) = 9
      // case 2 : check a vertex having minimum value in the graph and non-sorted cyclic vertices
      //          1 8 9 7 6 -> check (1) and (8,9,7,6) -> (1+6) + (1+9) + (1+7) + (1+8) + (1+6) = 41
      ans += min((cycle - 2* a[i].first, a[i].first + (cycle + 1* a[0].first);
   }
   printf("%lld", ans);
   return 0;
}
cs

 

 

이 댓글을 비밀 댓글로