반응형

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



아직 내공이 부족해서 한참 고민하고 겨우겨우 풀이한 문제였다.

핵심은 끝자리가 0일때와 1일때를 나누어 생각하는 것이고 n번째를 구하기 위해 n-1번째 값을 사용하기 위해 생각해 본 결과 점화식을 얻을 수 있었다. 또 점화식을 얻는데 중요한 힌트가 되었던 것은 문제 내에 식이 써있는 것도 많은 도움이 되었다.


dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1]

dp[n][k][1] = dp[n-1][k][0] + dp[n-1][k-1][1]


소스코드

 //

//  main.cpp

//  Algorihm

//

//  Created by sw on 2018. 9. 10..

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

//

#include <cstdio>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <queue>

#define MAX 101

using namespace std;

int n,k;

int dp[MAX][MAX][2];

queue<int> q;

void solve(int n, int k){

    dp[1][0][0]=dp[1][0][1]=1;

    for(int i=2;i<=n;i++){

        for(int j=0;j<i;j++){

            dp[i][j][0] = dp[i-1][j][0]+dp[i-1][j][1];

            dp[i][j][1] = dp[i-1][j][0]+dp[i-1][j-1][1];

        }

    }

    q.push(dp[n][k][0]+dp[n][k][1]);

}

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

    int tc;

    scanf("%d",&tc);

    while(tc--){

        scanf("%d %d", &n, &k);

        memset(dp,0,sizeof(dp));

        solve(n,k);

    }

    //출력

    while(!q.empty()){

        cout<<q.front()<<endl;

        q.pop();

    }

    return 0;

}


반응형

'Algorithm' 카테고리의 다른 글

[Algospot] PI 원주율 외우기  (0) 2018.09.19
[Algospot] TRIANGLEPATH 삼각형 위의 최대 경로  (0) 2018.09.17
[BOJ 2167] 2차원배열의 합 구하기  (0) 2018.09.07
[BOJ 11048] 다리놓기  (0) 2018.09.07
코딩인터뷰  (0) 2018.08.10
반응형

다형성


OOP에서의 다형성은 여러 가지 형태를 가질 수 있는 능력을 말하며, 자바에서는

한 타입의 참조변수로 여러 타입의 객체를 참조할 수 있도록 함으로써 다형성을 프로그램적으로 구현했다.


즉 조상클래스 타입의 참조변수로 자손클래스의 인스턴스를 참조할 수 있도록 했다는 것이다.


class Home{

  String address;

  boolean isVisit;

  

  void rest();

  void eat(); 

}

class Room extends Home{

  String roomName;

  

  void sleep();

}


Home 과 Room은 서로 상속관계에 있으며 다음과 같이 사용할 수 있다.

Home home = new Room();

Room room = new Room();


이 코드에서 Room인스턴스 2개를 생성하고 참조변수 home,room이 생성된 인스턴스를 하나씩 참조하도록 했다.

이 경우 인스턴스가 Room타입이여도 참조변수 home은 room의 모든 멤버를 사용할 수 없다. 즉, 둘 다 같은 타입의 인스턴스지만 참조변수의

타입에 따라 사용할 수 있는 멤버의 갯수가 달라지는 것이다. 


반대로 Room r = new Home()은 불가능하다. 왜냐하면 실제 인스턴스 r이 사용할수 있는 멤버 갯수가 실제 인스턴스인 Home의 갯수보다 더 많기 때문이다.

참조변수가 사용할 수 있는 멤버의 개수는 인스턴스의 멤버 개수보다 같거나 적어야 하는 것이다. 왜냐하면 클래스는 상속을 통해 확장되는 것이지

축소될 수는 없기 때문이다. 조상 인스턴스의 멤버 개수는 자손 인스턴스의 멤버 개수보다 항상 적거나 같기 때문에 반대의 경우는 불가하다.


그렇다면 어차피 조상타입으로 선언하면 조상타입의 멤버만 참조가능할텐데 왜 일부 멤버만을 사용하도록 하는 것일까??


그 이유는 참조변수도 상속관계에 있는 클래스 사이에서는 형변환이 가능하기 때문이다. 자손타입의 변수를 조상타입으로 조상타입의 변수를 자손타입으로 변환할 수 있다.

따라서 모든 객체는 Object클래스 타입으로 형 변환이 가능하다.


형 변환에서 자손 -> 조상을 Up-casting

           조상 -> 자손을 Down-casting 이라고 하며 up은 생략이 가능하지만 down-casting은 형변환 생략이 불가하다.


그 이유는 조상타입 참조변수가 참조하는 것은 조상타입이거나 자손타입일 것이다. 즉 참조변수가 다룰 수 있는 멤버의 개수가 실제 인스턴스가 가지고 있는 멤버 개수보다 적을 것이 분명하므로 문제가 되지 않기 때문이다.

반응형
반응형

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



#include <iostream>

#define MAX 301

int N,M,K;

int dp[MAX][MAX];


using namespace std;

void getSum(){

int value;

cin>>N>>M;

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

for(int j=1;j<=M;j++){

cin>>value;

dp[i][j]=value + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];

}

}

cin>>K;

while(K--){

int x1,y1,x2,y2;

cin>>x1>>y1>>x2>>y2;

cout<<dp[x2][y2] -(dp[x1-1][y2] + dp[x2][y1-1] - dp[x1-1][y1-1])<<endl;

}

}

int main(){

getSum();

return 0;


차근차근 생각하면 어렵지 않은 문제 

어렵다면 그림을 그려보자

dp[i][j]를 구할때 중복되는 값이 있다는 것을 인지한다면 쉽게 풀 수 있다.

반응형

'Algorithm' 카테고리의 다른 글

[Algospot] TRIANGLEPATH 삼각형 위의 최대 경로  (0) 2018.09.17
[BOJ 2698] 인접한 비트의 개수  (0) 2018.09.10
[BOJ 11048] 다리놓기  (0) 2018.09.07
코딩인터뷰  (0) 2018.08.10
깊이 우선 탐색(DFS, Depth First Search)  (0) 2018.08.08

+ Recent posts