Skip to content
kkw
조회 수 21 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

문제: www.acmicpc.net/problem/2775
 

문제요약:

a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와야한다고 가정했을때  k층에 n호에는 몇 명이 살고 있는지 계산해라!

단) 아파트는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

 

알고리즘:

규칙을 찾기 위해 다음과 같은 표를 짜 본다

 

 

층수

호수

0

1,2,3,4,5

1

1,3,6,10,15

2

1,4,10,20,35

3

1,5,15,35,70

4

1,6,21,56,123

5

1,7,28,84,246

 

 

a층의 b호= a층(b-1)호 +(a-1)층 b호인 규칙을 발견 할 수 있다

 

KakaoTalk_20190812_001619669.png

 

예외인 0층만 제외하면 완성이다?

 

<소스코드>

 

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
    #include<iostream>
 
    using namespace std;
 
    int sn[1000= {0,};
    int cn = 0;
    
    void test(int k, int n)
    {
        int ka[15= { 0, };
        int kb[15= { 1 };
 
        if (k == 0)
        {
            sn[cn] = n;
            cn++;
        }
 
        else
        {
            for (int i = 0, j = 1; i < n; i++, j++)
                ka[i] = j;
 
            for (int j = 0; j < k; j++)
            {
                for (int i = 0; i < n; i++)
                    kb[i + 1= ka[i + 1+ kb[i];
 
                for (int i = 0; i < n; i++)
                    ka[i] = kb[i];
            }
            sn[cn] = kb[n];
            cn ++ ;
        }
 
    }
 
 
    int main()
    {
        int t;
        int k, n;
    
        cin >> t;
    
        while (t--)
        {
            cin >> k >> n;
            test(k,n);
        }
        for (int i = 0; i < cn; i++)
            cout << sn[i] << "\n";
    }
cs

 

 

 

 

?

2019.08.10 01:09

백준 10250번 ACM 호텔

kkw
조회 수 25 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

문제:  www.acmicpc.net/problem/10250

 

문제 요약:  

엘리베이터로 부터 가장 가까운 방 부터 손님을 채웠다고 가정했을때 다음과 같이 호텔의 층수(H), 각층의 방수(W)가 주어졌다.  N번째 손님은 어느 방에서 묶을까?

 

 

문제 알고리즘:  

이번 문제는 생각보다(?) 쉬웠다... 단계 별로 푸는 문제인데 어째서 Fly me to the Alpha Centauri 가 가장 어렵다고 느꼇다.

 

우선 가장 가까운 방 부터 손님을 채웠으니까 H/N을해서 나누어 떨어지는 경우 H만큼,

나누어 떨어지지 않는 경우 H%N의만큼 높이가 올라갈것이다. 이를 통해 손님이 몇층에 사는지 알수있다. 또한 호텔의 가로 길이는 0부터가 아닌 1부터 시작하기떄문에 나눈 값에 +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
#include<iostream>
 
using namespace std;
 
 
int main()
{
    int h, w, n,k;
 
    cin >> k;
    
    while (k--)
    {
        cin >> h >> w >> n;
        
        if (n%h==0)
        {
            if (n/h>=10)
                cout << h << n/ h<<"\n";
            
            else
                cout << h<<"0"<< n / h << "\n";
        
        }
        
        else
        {
            if (n/h+1 >= 10)
                cout << n % h << n / h+1 << "\n";
        
            else
                cout << n % h <<"0"<< n / h+1 << "\n";
            
        }
        
    }
    
 
}
 
 
cs

 

 

 

?

kkw
조회 수 32 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

문제 : https://www.acmicpc.net/problem/2869

 

 

문제요약:

낮에는 Am 이동하고 잠잘때 Bm 내려간다 하지만 정상에 올라갔을시 내려가지 않을시 Vm 이동하는데 몇일이 걸리는가?

 

 

알고리즘:

 

처음에는 (V-A)를 통해서 거리를 줄이고 (A-B)를 통해서 하루에 얼마나 이동할 수 있는지 계산한 후 이 값을 계속해서 뺴주는 방식으로 알고리즘을 짯었다. 이론상? 완벽하나 이 문제의 경우 제한시간이 0.15초여서 큰 수의 경우 시간제한에 걸려버린다.

 

따라서 우리는 규칙을 찾아서 해결해야한다

 

시도 1 (실패)

                         ((v-a)/(a-b))반올림 +1이란 공식을 시도 했으나

                                                            20 3 45의 반례가있어서 실패하였음

 

시도 2 (성공)

                      (v-a)/(a-b) 나머지가 없으면 +1 추가

                        (v-a)/(a-b)나머지가 있으면 +2 추가

 

 

<소스코드 >

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cmath>
using namespace std;
 
int main()
{
    int a, b, v;
 
    cin >> a >> b >> v;
    
    if ((v - a) % (a - b) == 0)
        cout << (v - a) / (a - b)+1;
    else
        cout << (v - a) / (a - b)+2;
 
    
 
 
}
 
 
cs

 

 

 

 

 

 

 

?

kkw
조회 수 33 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

문제:https://www.acmicpc.net/problem/1011

 

 

 

문제요약:

x지점에서 부터 y지점까지 매번 k, k-1, k+1 으로 이동 할 수 있다 가정 했을때 최소한의 횟수로 이동하여라! 단, 처음과 마지막 이동은 1 만큼만 이동할 수 있다. 

 

 

알고리즘:

 

처음에는 그라디 알고리즘 문제를 풀듯이 매번 선택지에서 가장 거리를 줄일수 있는 선택지를 선택하는 방식으로 문제를 풀었다 백준에서 예제로 준 문제도 잘 출력되길레 성공을 확신했으나

결과는 시간초과 ㅜㅜ 시간초과 죽었으면...    후에 안 사실이지만 알고리즘 또한 틀렸다...

 

1)우선 x와 y좌표간의 이동하는 거리의 총량이 중요하므로 우선 거리를 구하기 위해 y-x를 해준다.

 

2) 규칙을 찾는다  

 

아래의 표는 거리에 따른 항로와 공간이동장치 회수를 표로 나타낸것이다

 

 

거리

항로

이용횟수

1

1

1

2

1-1

2

3

1-1-1

3

4

1-2-1

3

5

1-2-1-1

4

6

1-2-2-1

4

7

1-2-2-1-1

5

8

1-2-2-2-1

5

9

1-2-3-2-1

5

10

1-2-3-2-1-1

6

11

1-2-3-2-2-1

6

12

·

6

13

·

7

14

·

7

15

·

7

16

1-2-3-4-3-2-1

7

 

 

위의 표에서 눈치챘겠지만 다음과 같은 규칙이 나온다!

 

 

제곱

항로

회수

1

1

1

4

1-2-1

3

9

1-2-3-2-1

5

16

1-2-3-4-3-2-1

7

 

이를 통해서 이동하는 거리의 총량이 n의 제곱과 같을때

최소한의 이용횟수는 2*n-1이란 공식이 만들어진다!

 

항로.PNG

 

위 표를 통해서 dist-n<=x<=n*n 까지는 2*n-1이 되고  범위에 포함하지 않는 수는 2*n-2 공식이 성립한다.

 

개인적으로 내가 푼 문제중에서 가장 어려웠다 ㅜㅜ 이 문제를 푸는데 대략 2~3시간 정도 걸린것 같다.

막상 성공한 소스코드를 보니깐 허무? 하기도 하고 규칙을 막상 찾으니깐 이런 쉬운 문제를 왜이리 오래걸렸을까 ㅋㅋㅋ 

 

<성공 소스코드>

 

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
#include<iostream>
 
using namespace std;
 
int dt(int dist)
{
    long long i=1;
 
 
    while (i * i <= dist)i++;
 
    if ((i-1)*(i-1== dist)
        return 2*(i-1- 1;
    else if ((i*i-i)+1 <=dist)
        return 2 * i - 1;
    else
        return 2 * i - 2;
 
 
}
 
int main()
{
    int x,y;
    int t;
    int num;
    
    cin >> t;
    
    while(t--)
    {
        cin >> x >> y;
        num=dt(y - x);
        cout << num<<"\n";
    }
}
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
#include<iostream>
 
using namespace std;
 
int num[100000];
int ho = 0;
 
void warp(int dis)
{
    int k = 1, sk, bk;
    int cnt = 0;
 
    while (0 != dis)
    {
        cnt++;
        sk = k - 1;
        bk = k + 1;
 
        if (0 <= (dis - bk))
        {
            dis -= bk;
            k = bk;
        }
        else if (0 <= dis - k)
            dis -= k;
        else
        {
            dis -= sk;
            k = sk;
        }
    }
    
        num[ho] = cnt + 2;
        ho++;
}
 
 
int main()
{
    int repeat;
    int x, y;
    cin >> repeat;
 
    for (int i = 0; i < repeat; i++)
    {
        cin >> x >> y;
        warp((y - x) - 2);
    }
 
    for (int i = 0;i<repeat; i++)
    {
        cout << num[i]<<"\n";
    }
 
}
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
#include<iostream>
 
using namespace std;
 
int dt(int dist)
{
    int i;
    int temp = 0;
 
    for (i = 0; temp < dist; i++)
        temp = i * i;
 
    if (temp == dist)
        return 2 * i - 3;
    else
        return 2 * i - 4;
 
 
}
 
int main()
{
    int x,y;
    int rep;
    int num;
    
    cin >> rep;
    
    for (int i=0 ;i<=rep; i++)
    {
        cin >> x >> y;
        num=dt(y - x);
        cout << num<<"\n";
    }
}
cs

 

 

 

?

kkw
조회 수 30 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

 

문제: https://www.acmicpc.net/problem/1193

 

 

문제요약: 

 

지그재그 순으로 차례로 1번 2번 3번 분수라고 했을시 X번째 분수를 구하여라!

 

 

 

알고리즘:

 

분수찾기 - 복사본 (2).PNG

 

1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3  순으로 순서가 정해진다

 

 

 분수찾기 - 복사본.PNG

빨간선 : 홀수 파란선 :짝수                                          이를 대각선으로 줄을 그어 보면

 

 

 

제목 없음.png

 

짝수일때는 순번이 낮을수록 분모의 크기가 커지고 분자의 크기가 줄어드는것을 알수있다.

홀수일때는 순번이 낮을수록 분모의 크기가 줄어들고 분자의 크기가 커지는것을 알 수 있다

 

 

 

KakaoTalk_20190803_000902806.jpg

 

즉! X번쨰의 분수가 몇번쨰 대각선줄에 있는지, 그 대각선에서 순서가 가장 늦은 수를 알 수 있다면 x번쨰의 분수를 알수 있을것이다

 

 

<소스코드>

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<iostream>
 
using namespace std;
 
int main()
{
    int num;
    int cnt = 0//마지막수
    int ho = 1//대각선
    int val; //뺴줄 때 쓰는 변수 꼭 필요한건 아님 
    
    cin >> num;
 
    while (1)
    {
        for (int i = 1; i <= ho; i++)
            cnt++;
 
        if (num <= cnt)
            break;
        ho++;
    }
 
    val = cnt - num;
    
    if (ho % 2 == 0)
    {
        cout<<ho-val<< "/"<<ho-(ho-val-1);
    }
    else
    {
        cout << ho - (ho - val - 1<< "/" << ho - val;
    }
 
}
 
 
cs

 

?

2019.08.01 17:21

백준2292번 벌집 문제

kkw
조회 수 27 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

문제: https://www.acmicpc.net/problem/2292

 

 

문제요약: 

벌집의 중앙 1에서 N번 방까지 최소로 방을 지나갈때 몇 개의 방을 지나가는가

 

 

알고리즘: 

제목 없음.png

 

1칸 6칸 12칸 · · · 6칸씩 늘어가는 것을 알 수 있다.

 

1 1칸
1<n<=7 2칸
7<n<=19 3칸
19<n<=37 4칸

 

전  카운트수 <n <n+=6*count까지의 수인것을 알수있다

 

<소스코드>

 

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<iostream>
 
using namespace std;
 
int main()
{
    int num;
    int temp;
    int n=1;
    int ct=1;
 
    cin >> num;
    
    if (num == 1)
    {
        cout << num;
    }
 
    else
    {
        while (1)
        {
            temp = n;
            n += 6 * ct;
            ct++;
 
            if (temp < num&& num <= n)
            {
                cout << ct;
                break;
            }
 
        }
    }
 
}
 
 
cs

 

 

?

kkw
조회 수 25 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

문제 : https://www.acmicpc.net/problem/2839

 

 

 

문제요약 :  

무작위로 주어진 Nkg의 설탕을 3kg을 담을 수 있는 봉지와 5kg을 담을 수 있는 봉지를 최소한으로 사용하여 설탕을 담으라!

 

 

출력 : 

봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

 

알고리즘 :

 

우선 N킬로그램을 만들수 없는 경우부터 생각해야 한다! 이 경우를 알기 위해선 수학적 귀납법이 필요하다. 

우선 Nkg을 3g과 5g으로 만들수 있다고 가정하자 그렇다면 Nkg+3kg 또한 만들 수 있을것이다.

 

Nkg+1 만들 수 있다면 Nkg+4도 가능하다

Nkg+2 만들 수 있다면 Nkg+5도 가능하다

Nkg+3 만들 수 있다면 Nkg+6도 가능하다

 

이런 방식으로 n에서 부터 연속으로 3개 이상을 만들수 있다면 N값 이상 부터의 모든 수는 3과 5로 만들 수 있을 것이다.

n

n+3

가능여부

3

6

4

7

5

8

6

9

7

10

8

11

9

12

10

13

 

따라서 8이상의 모든 수는 3과 5의 조합으로 만들수 있다는것을 귀납적으로 증명하였다.

 

다음으로 탐욕(그라디)알고리즘을 통해서 사용하는 봉지의 수를 최소한으로 만들어야한다. 

 

가장 많은 양을 담을 수 있는 5kg 봉지를 최대한 사용한다. 5kg을 최대한 사용한후 나누어떨어지지 않는다면 나머지가 3에 나누어떨어질때까지 5kg봉지의 사용량을 -1씩 줄여간다.

KakaoTalk_20190731_213906626.jpg

 

 

 

<소스코드>

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<iostream>
 
using namespace std;
 
int main()
{
    int a,j,k;
    int count = 0
    
    cin >> a;
    if (a == 4 ||a==7)
        cout << -1;
    else
    {
        j = a / 5;
        while (1)
        {
            if ((a - (5 * j)) % 3 == 0)
            {
                cout << j + ((a - (5 * j)) / 3);
                break;
            }
            j--;
        }
    }
 
}
 
 
cs
?

kkw
조회 수 27 추천 수 0 댓글 1
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

문제: https://www.acmicpc.net/problem/1712

 

문제 요약:

고정비용(A) 가변비용(B) 판매비용(c)가 주어졌을시 최초로 총 수입(판매비용)이 총 비용(고정비용+가변비용)보다 많아져 이익이 발생하는 구간(손익분기점)을 구하라

 

출력:

첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익분기점이 존재하지 않으면 -1을 출력한다.

 

문제 알고리즘:

판매비용<=가변비용일 경우에  이익이 발생 할수 없으므로 -1을 출력한다

판매비용>가변비용일 경우 (a/(c-b))+1이 성립한다

 

 

소스코드:

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;
 
int main()
{
 
int a, b, c;
 
cin >> a >> b >> c;
 
if (c - b <= 0
{
cout << -1 << endl;
}
 
else
{
cout << a / (c - b) + 1 << endl;
}
 
cs

 

 

 

?
  • ?
    맹주완 2019.07.29 23:25
    음 완전 수학문제이군!
    알고리즘은 수학문제로 시작하는거니깐은!! 이젠 막걸리 문제도 한번 풀어서 리뷰해볼까?

Board Pagination Prev 1 Next
/ 1

Powered by Xpress Engine / Designed by Sketchbook

sketchbook5, 스케치북5

sketchbook5, 스케치북5

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소