'분류 전체보기' 카테고리의 글 목록

오늘의 문제는 다음과 같다.

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스 마다 P(N)을 출력한다.

예제 입력

2
6
12

예제 출력

3
16

법칙을 파악하면 풀 수 있는 문제로 생각된다 ㅠㅠ

코드는 아래와 같다.

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] 2965 캥거루 (0)	2018.01.17
[boj] no.1475 room number (0)	2017.12.23
[boj]no.2292 벌집 (0)	2017.12.07
[boj]1004 어린왕자 (0)	2017.12.04
[boj] no.1003 피보나치 (0)	2017.12.01

문제가 생각보다 간단하게 풀려서 굉장히 당황스러움..;;;

이러려고 이 문제를 택한 것은 아닌뒙;

어쨋든 오늘의 문제는 ?

문제

캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다.

한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다.

캥거루는 최대 몇 번 움직일 수 있을까?

입력

첫째 줄에 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100)

출력

캥거루가 최대 몇 번 움직일 수 있는지 출력한다.

예제 입력

3 5 9

예제 출력

이에 따른 코드는 아래와 같다!!

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] 9461파도반 수열 (1)	2018.01.19
[boj] no.1475 room number (0)	2017.12.23
[boj]no.2292 벌집 (0)	2017.12.07
[boj]1004 어린왕자 (0)	2017.12.04
[boj] no.1003 피보나치 (0)	2017.12.01

6과 9는 구분없이 사용함으로 이것만 신경쓰면 오키

#include <stdio.h>
#include <string.h>
#define max(a,b) (a)>(b)?(a):(b)

int answer, tmp, cnt[10];
char str[10];

int main() {
    scanf("%s", str);
    
    for (int i = 0; i < strlen(str); i++) cnt[str[i] - '0']++;
    for (int i = 0; i <= 9; i++) if (i != 6 && i != 9) ans = max(answer, cnt[i]);
    
    ans = max(answer, (cnt[6] + cnt[9] + 1) / 2);
    
    printf("%d", answer);

    return 0;
}

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] 9461파도반 수열 (1)	2018.01.19
[boj] 2965 캥거루 (0)	2018.01.17
[boj]no.2292 벌집 (0)	2017.12.07
[boj]1004 어린왕자 (0)	2017.12.04
[boj] no.1003 피보나치 (0)	2017.12.01

짧은 코드로 완셩!!!

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] 2965 캥거루 (0)	2018.01.17
[boj] no.1475 room number (0)	2017.12.23
[boj]1004 어린왕자 (0)	2017.12.04
[boj] no.1003 피보나치 (0)	2017.12.01
[boj] no.1074 Z (2) (0)	2017.11.30

1dP에서 본 어린왕자 문제를 풀어보았다.

이해하고 있었던 문제라 어려움이 없었다.

#include <stdio.h>

#include <math.h>

int main()

{

int test_case;

int x1,x2,y1,y2;

int cnt = 0;

int cx, cy, r;

int ast;

double dist1, dist2;

scanf("%d", &test_case);

while(test_case--){

scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

scanf("%d", &ast);

while (ast--) {

scanf("%d %d %d", &cx, &cy, &r);

dist1 = abs(x1-cx) + abs(y1-cy);

dist2 = abs(x2-cx) + abs(y2-cy);

if(dist1 <= r && dist2 <=r) continue;

else if(dist1 <= r) cnt++;

else if(dist2 <= r) cnt++;

}

printf("%d\n", cnt);

}

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] no.1475 room number (0)	2017.12.23
[boj]no.2292 벌집 (0)	2017.12.07
[boj] no.1003 피보나치 (0)	2017.12.01
[boj] no.1074 Z (2) (0)	2017.11.30
[boj] no.2775 부녀회장이 될테야 (0)	2017.11.29

ㅠ0ㅜ ...피보나치!

문제

다음 소스는 N번째 피보나치 함수를 구하는 함수이다.

int fibonacci(int n) {
    if (n==0) {
        printf("0");
        return 0;
    } else if (n==1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.

두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.

fibonacci(0)은 0을 출력하고, 0을 리턴한다.

fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

이 때, 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

첫째 줄에 N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력

예제 출력

1 0
0 1
1 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
#include <stdio.h>
#include <stdlib.h>
int zero, one;
int fibonacci(int n)
{
    if (n==0) {
        zero++;
        return 0;
    } else if (n==1) {
        one++;
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
int main()
{
    int i, fi;
    int test = scanf("%d", &test);
    int n;
    
    while(scanf("%d",&n)!=EOF){
        fi = fibonacci(n);
        printf("%d %d\n", zero, one);
    }
    return 0;
}
Colored by Color Scripter
cs

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj]no.2292 벌집 (0)	2017.12.07
[boj]1004 어린왕자 (0)	2017.12.04
[boj] no.1074 Z (2) (0)	2017.11.30
[boj] no.2775 부녀회장이 될테야 (0)	2017.11.29
[boj] no.1074 z (2)	2017.11.28

저번에 못풀었던 문제를 다시 풀었어요.

분할 정복 형식으로 풀고, 재귀 함수를 이용하였습니다!!

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

2 3 1

예제 출력

출처: https://www.acmicpc.net/problem/1074

아래의 소스를 참고하세욧!!

오랜만에 비트 shift도 썼네... 헷... 뿌듯합니다.

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>
 
int n, r, c;
int go(int length, int x, int y)
{
    //length:행(열)의 개수, x: current row, y: current cloumn
    //재귀를 멈추기 위한 제약식
    if (length == 1) return 0;
    //bound: 사분면의 경계
    int bound = length >> 1;
    //사분면 최소값을 더해주기 위한 변수
    int min = bound * bound;
 
    if(x < bound && y < bound) return go (bound, x, y);
    else if (x < bound && y >= bound) return min + go(bound, x, y - bound);
    else if (x >= bound && y < bound) return min * 2 + go(bound, x - bound, y);
    return min * 3 + go(bound, x - bound, y - bound);
}
int main()
{
        scanf("%d%d%d", &n,&r,&c);
        printf("%d", go(1 << n, r, c));
}
Colored by Color Scripter
cs

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj]1004 어린왕자 (0)	2017.12.04
[boj] no.1003 피보나치 (0)	2017.12.01
[boj] no.2775 부녀회장이 될테야 (0)	2017.11.29
[boj] no.1074 z (2)	2017.11.28
[boj] no.1002 터렛 (1)	2017.11.27

오늘의 문제는 제목도 짱 귀여운!!!! 부녀회장이 될테얌!

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a 층의 b 호에 살려면 자신의 아래(a-1)층에 1호부터 b 호까지 사람들의 수의 합만큼 사람들을

데려와 살아야한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정 했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호

에는 몇 명이 살고 있나를 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층에 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다.

(1 <= k <= 14, 1 <= n <= 14)

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

예제 입력

예제 출력

6
10

출처: https://www.acmicpc.net/problem/2775

문제를 푸는데에 동적할당을 사용하였다.

백준에서는 ... 런타임 오류가 뜬다...

ㅠㅜ 고민해봐야겠댜... ㅠㅠ

<풀이>

다이나믹 프로그래밍을 사용하면 된다.

큰 문제를 작은 문제로 나눠서, 구한 작은 값들을 저장하여 큰 값을 구하는 것이다.

점화식은 아래의 코드에서 확인하세요!

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
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char const *argv[]) {
    int T,k,n;//T:test case,k:floor,n:room
    int i,j;
    int **ptr;//동적할당 포인터
    scanf("%d",&T);
    while(T){
        scanf("%d %d",&k,&n);
        //2차원 배열 동적할당
        ptr = (int**)malloc(sizeof(int*)*(k+1));
        for(i=0;i<=n;i++)   ptr[i] =(int*)malloc(sizeof(int)*(n+1));
        //0F의 사람수 자동입력
        for(i=0;i<=n;i++)   ptr[0][i] = i;
        //매층의 0호는 존재하지 않는다.
        for(i=0;i<=k;i++)   ptr[i][0] = 0;
        //점화식
        for(i=1;i<=k;i++){
            for(j=1;j<=n;j++)   ptr[i][j] = ptr[i-1][j] + ptr[i][j-1];
        }
        printf("%d\n",ptr[k][n]);
        T--;
        //포인터 끊기
        if(T) ptr = NULL;
    }
    for(i=0;i<=n;i++) free(ptr[i]);
    free(ptr);
    return 0;
}
Colored by Color Scripter
cs

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] no.1003 피보나치 (0)	2017.12.01
[boj] no.1074 Z (2) (0)	2017.11.30
[boj] no.1074 z (2)	2017.11.28
[boj] no.1002 터렛 (1)	2017.11.27
[boj] no.2448 별찍기!! (0)	2017.11.23

오늘의 문제는 햄숙이와 함께 시도했다.....

그러나 다 풀지 못했돠... ㅠㅠ

일찍 일찍 시작하자.. ㅠㅠ

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

2 3 1

예제 출력

출처: https://www.acmicpc.net/problem/1074

오늘은 재귀함수 문제를 풀어볼라고 시도했는데, 알고리즘을 짜는데 막히는 부분이 있었습니다.. ㅠㅠ

아무래도 생각을 길게 안하고 풀려고 하다가 보니 그런게 아닐까나.... 일단 오늘까지 한 부분은 아래와 같습니다.

마지막 결과를 어떻게 도출할 지만 함수에 포함하고 재귀함수를 불러오는 부분을 어떻게 짤지는 좀더 생각해 봐야겠습니다.

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
#include <stdio.h>
int bound=0;
 
int main(int argc, char const *argv[]) {
  int N,r,c,arr,num,bound;
  int **ptr;
  int i,j;
 
  scanf("%d", &N);
  ptr = (int**)malloc(sizeof(int*)*N);
  for (i = 0; i < N; i++) {
    ptr[i] = (int*)malloc(sizeof(int)*N);
  }
  
 
 
 
  for (i = 0; i < N; i++) {
    free(ptr[i]);
  }
  free(ptr);
  
  return 0;
}
int cal(int N){
  //마지막 결과 값 도출
  if (N==1) {
    if (r<bound&&c<bound) {
      num = bound;
    } else if (r<bound&&c>=bound) {
      num = bound + 1;
    } else if (r>=bound&&c<bound) {
      num = bound + 2;
    } else {
      num = bound + 3;
    }
  } else { //재귀함수
    bound = 
  }
  
}
Colored by Color Scripter
cs

1DP를 아침에 꼭 시작하겠다는 마음을 다지는 하루....

인생 올바르게 살아야 안되긋나... 싶네요.... 퓹퓹 ㅠㅠ

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] no.1074 Z (2) (0)	2017.11.30
[boj] no.2775 부녀회장이 될테야 (0)	2017.11.29
[boj] no.1002 터렛 (1)	2017.11.27
[boj] no.2448 별찍기!! (0)	2017.11.23
[boj] no.1152 단어의 개수 (0)	2017.11.22

문제

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

아아아아아니 터렛이라니, 문제보고 놀랐다는... 터렛이라니...ㅋㅋㅋ 게다가 터렛은 인구수에도 안들어간다는 저 친절한 해설 덕분에 이문제가 하고싶어졌다...

이 문제를 보면 느닷없이 힌트가 있다는 것을 눈치챈 분도 있을 것이다!!!..... r1, r2라니... 왠지 반지름 같지 아니한가.......큐큐큐 히히힣히

두 원의 접점에 대한 이론을 우리는 교육 과정 속에서 언젠간 배웠다는것......?!?!

확인해보니... 엄... 중학 수학에도 있다고함....ㅎㅎ... 멘붕...

참고: http://mathbang.net/101

여튼 그렇게 해서, 만들어 내면 되욥!

자세한 내막은 코드를 보시라!

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>
#include <stdlib.h>
#include <math.h>
 
int main(int argc, char const *argv[]) {
  int i,test;
  int x1,y1,r1,x2,y2,r2,dist;
  //조규현 좌표(x1,y1),백승환 좌표(x2,y2), 각각의 류재명 까지의 거리 r1,r2, 조규현과 백승환 거리
  int *cnt;
  //가능한 류재명 좌표의 개수, 조규현과 백승환의 거리
  scanf("%d", &test);
  cnt = (int*)malloc(sizeof(int)*test);
  for (i = 0; i < test; i++) {
    scanf("%d %d %d %d %d %d", &x1,&y1,&r1,&x2,&y2,&r2);
    dist = abs(x1-x2) + abs(y1-y2);
 
    if (dist == 0) { //조규현과 백승환이 같은 위치인 경우
      if (r1==r2) {
        cnt[i] = -1;
      } else {
        cnt[i] = 0;
      }
    } else { //조규현과 백승환이 다른 위치인 경우
      if ((r1+r2)<dist) {
        cnt[i] = 0; 
      } else if ((r1+r2)==dist) {
        cnt[i] = 1;
      } else {
        cnt[i] = 2;
      }
    }
  }
  for (i = 0; i < test; i++) {
    printf("%d\n", cnt[i]);
  }
  return 0;
}
Colored by Color Scripter
cs

오늘도 완성!!! 뀨뀨 ㅎㅎㅎㅎ

오늘 하루도 고생했어 모두모두 :)

'알고이즘 > 문제를 막풀어' 카테고리의 다른 글

[boj] no.2775 부녀회장이 될테야 (0)	2017.11.29
[boj] no.1074 z (2)	2017.11.28
[boj] no.2448 별찍기!! (0)	2017.11.23
[boj] no.1152 단어의 개수 (0)	2017.11.22
[boj] no.11720 숫자의 합 (0)	2017.11.21