반응형

문제

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



문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생들이 구금되어있다.

그러던 어느날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. 같은 방식으로 n번의 라운드를 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5≤n≤100)이 주어진다.

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

예제 입력 1 

2
5
100

예제 출력 1 

2
10







   



문제 풀이

테스트 케이스는 5이상 100이하이다.

즉 방이 최소 5개 존재한다는 것이다. 처음에 문제를 이해할 때는 짝수 번째는 2의 배수 홀수 번째는 3의 배수로 풀이하다가 잘못된 것을 알고

2번째는 2의 배수, 3번째는 3의 배수 4번째는 4의 배수, n번째는 n의 배수임을 깨닫게 되었다.


n = 5인 경우 (1 = open / 0 = close)


  1 

1 

1 

1 

1 

 1

0 

1 

0 

1 

 1

0 

0 

0

1 

 1

0 

0 

1 

1 

 1

0 

0 

1 

0


위 표를 보면 규칙이 각 라운드 마다 열거나 닫는 방 번호는 라운드의 배수임을 알 수 있다. 

즉, 방번호 % 라운드 == 0 인 경우 열린 문은 닫고, 닫힌 문은 열면 되는 간단한 문제이다.

if문을 사용해서 방번호 %라운드 ==0 조건을 사용해도 되지만 조건을 조금 더 간단하게 하는 방법이 있다.

해당 라운드의 배수인 방이 열려있으면 닫고 닫혀있으면 여는 방법이다.

충분히 생각해보고 소스코드를 참고하자


소스코드

//

//  main.cpp

//  Algorithm

//

//  Created by sw on 2018. 6. 25..

//  Copyright © 2018년 sw. All rights reserved.

//


#include <iostream>

#include <algorithm>


using namespace std;

int main(int argc, const char * argv[]) {

    // insert code here...

    int testcase, room;

    cin>>testcase;

    while(testcase>0){

        testcase--;

        cin>>room;

        int dp[101] = {0};  //dp 저장 변수(테스트케이스마다 초기화를 위해 while문 안에 선언)

        for(int i=1;i<=room;i++){

            for(int j=1; i*j<=room; j++){

                if(dp[i*j]==1) dp[i*j]=0;

                else dp[i*j]=1;

            }

        }

        for(int i=1; i<=room; i++){

            dp[0] += dp[i]; //dp[0]를 count로 사용

                            //for문을 사용하고 싶지 않다면 위쪽 if문에서 dp[0]값을 더하거나 빼주면 됨.

        }

        cout<<dp[0]<<endl;  //문이 열린 갯수 출력

    }

    return 0;

} 



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

깊이 우선 탐색(DFS, Depth First Search)  (0) 2018.08.08
[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
[백준 1003] 피보나치 함수  (0) 2018.03.28
반응형

문제

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


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

위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 숫자는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1줄까지 숫자 삼각형이 주어진다.

출력

첫째 줄에는 최대가 되는 합을 출력한다.

입력

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


출력

30


먼저 N을 입력받고 이차원배열에 숫자삼각형을 입력한다.

그리고 나서 윗층과 누적할 이차원배열이 필요하다. 크기는 숫자삼각형 입력받은 것과 동일하며 

두 번째줄부터 윗줄과 더하고 그 누적값을 가지고 있어야한다.

맨 왼쪽일 경우, 맨 오른쪽일 경우, 중간에 있을 경우가 있다.

여기서 맨 왼쪽, 오른쪽은 상관없지만 중간에 있을 경우 가장 큰 것을 찾아야 한다.

그러면 중간 값은 자기보다 위 줄의 좌, 우에서 큰 값을 찾아야한다.

즉 자신의 위치에서 대각선 , 우의 최대값을 가져오면 되는 문제이다.


소스

//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 3. 30..

//  Copyright © 2018년 seungwoo. All rights reserved.

//


#include <iostream>

#include <algorithm>

using namespace std;


int dp[502][502];

int a[502][502];

int main()

{

    int n;

    

    cin>>n;

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=i; j++)

            cin>>a[i][j];

    }

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=i; j++)

            dp[i][j] = a[i][j] +  max(dp[i-1][j],dp[i-1][j-1]);

    }

    int res = 0;

    for (int i = 1; i <= n; i++)

        res = max(res, dp[n][i]);

    cout<<res;

    return 0;

}


 




반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1149] RGB거리  (0) 2018.03.29
[백준 1003] 피보나치 함수  (0) 2018.03.28
[백준 9095] 1,2,3 더하기  (0) 2018.03.27
반응형

문제

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



RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.


출력

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.


예제 입력

3
26 40 83
49 60 57
13 89 99


예제 출력

96


사실 알고리즘적 요소보다 문제 이해가 어려웠다.

문제 이해만 빠르고 확실하게 한다면 어려움없이 풀 수 있는 문제다.


만약 빨간집으로 시작했다면 2번째 집은 초록 or 파랑 이여만 한다.

즉 dp[0][1] (빨간색으로 칠했을때) = min(dp[1][i-1], dp[2][i-1])(전 집에서 초록색을 칠했을떄의 최소비용과 파란색으로 칠했을 떄의 최소비용 중 최소값) + r_cost (현재 i를 빨간색으로 칠했을때의 비용)

dp[1][1] (초록색으로 칠했을때) = min(dp[0][i-1], dp[1][i-1])(전 집에서 빨간색을 칠했을떄의 최소비용과 파란색으로 칠했을 떄의 최소비용 중 최소값) + g_cost (현재 i를 초록색으로 칠했을때의 비용)

dp[2][1] (파란색으로 칠했을때) = min(dp[0][i-1], dp[1][i-1])(전 집에서 빨간색을 칠했을떄의 최소비용과 초록색으로 칠했을 떄의 최소비용 중 최소값) + b_cost (현재 i를 파란색으로 칠했을때의 비용)


와 같은 식으로 진행되는 것을 알 수 있다.


이와 같은 식으로 모든 비용을 구한 이후 최소값을 출력해주는 알고리즘이다.



소스


//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 3. 29..

//  Copyright © 2018년 seungwoo. All rights reserved.

//


#include <iostream>

#include <algorithm>


using namespace std;


int main(int argc, const char * argv[]) {

    int house;

    int result;

    int cost[3][1001]={0};

    cin>>house;

    for(int i=1; i<=house; i++){

        int r_cost, g_cost, b_cost;

        cin>>r_cost>>g_cost>>b_cost;

        cost[0][i] = min(cost[1][i-1] , cost[2][i-1]) + r_cost;

        cost[1][i] = min(cost[0][i-1] , cost[2][i-1]) + g_cost;

        cost[2][i] = min(cost[0][i-1] , cost[1][i-1]) + b_cost;

    }

    result = min(cost[0][house], min(cost[1][house],cost[2][house]));

    cout<<result;

    return 0;

} 


반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1003] 피보나치 함수  (0) 2018.03.28
[백준 9095] 1,2,3 더하기  (0) 2018.03.27

+ Recent posts

티스토리툴바