씅의 기록하는 개발노트

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <stack>

#include <queue>

#include <vector>

#include <functional>

#define MAX 100

#define INF 0x7fffffff

using namespace std;

int n, t[MAX][MAX];

int dp[MAX][MAX];

int solve(int y, int x)

{

if(y==n-1)

return t[y][x];

int& ret=dp[y][x];

if(ret != -1)

return ret;

return ret = max(solve(y+1,x), solve(y+1,x+1)) + t[y][x];

}

int main(void)

{

int height;

scanf("%d",&n);

while(n--)

{

memset(dp,-1,sizeof(dp));

scanf("%d",&height);

for(int i=0;i<height;i++)

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

scanf("%d",&t[i][j]);

cout<<solve(0,0)<<endl;

}

return 0;

}

 //

//  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;

}

#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;

} 

 //

//  main.cpp

//  Algorihm

//

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

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

//

#include <iostream>

#include <algorithm>

#define MAX 1001

int N,M;

int dp[MAX][MAX];

using namespace std;

int move(int x, int y){

    int value;

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

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

            cin>>value;

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

        }

    }

    return dp[x][y];

}

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

    cin>>N>>M;

    cout<<move(N,M)<<endl;

    return 0;

}

//풀이(C++) 

bool isUnique(string* str){

if(str->length() > 256) 

return false;

bool check[256];

for(int i=0;i<str->length();i++){

int index=str->at(i);

if(check[index]==true)

return false;

else

check[index]=true;

}

return true;

}

//reverse함수 구현

//문자열 str포인터를 인자로 받아 역순으로 값을 바꿈

//풀이(C++)

void reverse(char *str)

{

char *end = str;

char temp;

if(str)

{

while(*end)

{

++end;

}

--end; //마지막 null값 제외

while(str<end)

{

temp=*str;

*str++ = *end;

*end-- = temp;

}

}

}

        //순열 = 문자열 종류와 길이는 같고 배열된 순서는 다를 수 있음

//풀이(JAVA)

/*

* 가장 먼저 문자열의 길이를 비교한다.

* 이후 정렬을 통해 문자열 종류를 비교한다.

*/

public boolean isCheck(String str1, String str2)

{

if(str1.length() != str2.length())

return false;

return sort(str1).equals(sort(str2));

}

public String sort(String str)

{

char[] result=str.toCharArray();

java.util.Arrays.sort(result);

return new String(result);

} 

//풀이(C++)

void convert(char str[], int len)

{

int blank=0; //공백 개수

int strlen=len;

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

if(str[i]==' ')

++blank;

}

strlen+=(blank*2); //2자리 증가

str[strlen]='\0';

for(int i=len-1;i>=0;i--){

if(str[i]==' '){

str[strlen-1]='0';

str[strlen-2]='2';

str[strlen-3]='%';

strlen-=3;

}

else

{

str[strlen-1]=str[i];

strlen--;

}

}

cout<<str;

}

 1

 2

3 

 4

5 

6 

7 

 8

0 

1

1 

0 

0 

 0

0 

0 

1

0 

0 

1 

1 

0 

0 

0 

1

0 

0 

0 

0 

1 

1 

0 

0

1 

0 

0 

0 

0 

0 

1 

0

1 

0 

0 

0 

0 

0 

1 

0

0 

1 

0 

0 

0 

0 

1 

0

0 

1 

0 

0 

0 

0 

1 

0

0 

0 

1 

1 

1 

1 

0 

#include <iostream>

int vertex; //정점 갯수

int map[30][30], visit[30]; // map - 상호간 연결을 나타냄 

// visit - 방문 여부

void DFS(int t_vertex);

using namespace std;

int main()

{

int sVertex; // Start Vertex

int v1, v2;

cin>>vertex>>sVertex;

while(true)

{

cin>>v1>>v2;

if(v1 == -1 && v2 == -1) //무한루프 방지

break;

map[v1][v2] = map[v2][v1] = 1; // vertex 상호간 연결

}

DFS(sVertex);

return 0;

}

void DFS(int t_vertex)

{

visit[t_vertex] = 1; // visit vertex

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

if(map[t_vertex][i] == 1 && !visit[i])

{

cout<<t_vertex<<"에서 "<<i<<"로 이동합니다"<<endl;

DFS(i);

}

}

} 

//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 06. 28

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

//

#include <iostream>

#include <algorithm>

using namespace std;

long long fibo(int n);

int main()

{

int T,n;

cin>>T;

while(T>0)

{

T--;

cin>>n;

cout<<fibo(n)<<endl;

}

return 0;

}

long long fibo(int n)

{

static long long dp[68]={0};

if(dp[n]!=0) return dp[n];

if(n==0 || n==1) return 1;

else if(n==2) return 2;

else if(n==3) return 4;

return dp[n]=fibo(n-1) + fibo(n-2) + fibo(n-3) + fibo(n-4);

} 

  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

//

//  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;

} 

//

//  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;

}