Home algorithm dynamic programming 알고리즘) 백준 Baekjoon 6359번 만취한 상범

알고리즘) 백준 Baekjoon 6359번 만취한 상범

by sho59 1월 23, 2017

Read

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

ACM-ICPC > Regionals > North America > Greater New York Region > 2002 Greater New York Programming Contest B번

위 문제의 분류는 다이나믹 프로그래밍으로 되어있지만...
막상 풀어보면 그냥 구현 문제입니다.

n개의 방이 있고 위스키를 한잔하고 방이 열려있으면 닫고, 닫혀있으면 엽니다.
예를들어 위스키가 한잔일때(n=1), 1,2,3,4,..이고
두잔일때는(n=2) 2,4,6,8.. n=3일때는 3,6,9,12,...식으로 방을 체크합니다.

위 그림처럼 n=1일때는 모든 방이 열리고, 2, 3 순으로 증가할 때마다 해당 방이 열리거나 닫힙니다.

코드 상으로는 배열을 선언하여 변수 mul을 1로 설정하여 반복문을 실행할 때마다 n의 값을 곱해주고 반복문이 한번 수행될때마다 mul을 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
int main()
{
    int room[101];
    int t, n;
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
        int mul = 1;
        
        for (int i = 0; i < 101; ++i) {
            room[i] = 0;
        }
        
        for (int start = 1; start <= n; ++start)
        {
            if (mul*start > n)
                break;
            room[mul*start] = 1;
            mul += 1;
        }
        int cnt = 0;
        for (int start = 1; start <= n; ++start)
        {
            if (room[start] == 1)
                cnt++;
        }
        cout << cnt << endl;
    }
}
Colored by Color Scripter
cs

댓글 없음:

피드 구독하기: 댓글 ( Atom )