https://github.com/cutegus10

7/12

1929번

#include <stdio.h>

int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    int con = 1;
    for (int i = m; i <= n; i++) {
        if (i < 2) { 
            continue;
        }
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                con = 0;
                break;
            }
        }
        if (con == 1) {
            printf("%d\\n", i);
        }
        con = 1;
    }
    return 0;
}

7/20

15649번

#include <stdio.h>

int arr[9];
int used[9];
int N,M;

void dfs(int depth){
    if(depth==M){
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\\n");
        return;
    }
    for(int i=1; i<=N; i++){
        if(used[i]==0){
            used[i]=1;
            arr[depth]=i;
            dfs(depth+1);
            used[i]=0;
        }
    }
}

int main()
{
    scanf("%d %d", &N, &M);
    dfs(0);
    return 0;
}

7/28

4948번

#include <stdio.h>

int main(void)
{
    int N, cnt = 0;
    int i, j, arr[246913] = {0, };
    
    arr[0] = 1, arr[1] = 1;
    for(j = 2; j < 246913 / j; j++)
    {
        //j로 나눌 수 있는 이유?
        // j*j<246913 과 같은 의미임
        // 100이하 소수를 구해라고 하면 2*2, 2*3,..3*4...9*10, 10*1...10*9
        // 10*10여기까지 제외하기때문에  j*j 까지만 하면 됨.
        
        if(arr[j] == 1) continue;
        for(i = j * j; i < 246913; i += j)
            //2*3같은 경우는 그 전에 j=2에서 처리 될거라서
            // 3*3으로 시작하는것
            if(i % j == 0) arr[i] = 1;
    }
    scanf("%d", &N);
    
    while(N != 0)
    {
        cnt = 0;
        for(i = N + 1; i <= N * 2; i++)
            if(arr[i] == 0)
                cnt++;
        printf("%d\\n", cnt);
        scanf("%d", &N);
    }
    return 0;
}

8/4

10974번

#include <stdio.h>

char res[17];      //각 순열을 저장
void dpl(int depth) {
    int i;
    if (depth == N) {
        printf("%s", res);   //완료된 순열 출력
        return;
    }
    for (i = 1; i <= N; i++) {
        if (chk[i] == 1) continue;   //이미 사용했다면 건너뜀
        chk[i] = 1;                  
        res[2 * depth] = i + '0';           
        dpl(depth + 1);              //재귀
        chk[i] = 0;                  //백트레킹
        }
}

int main(void) {
    int i;
    scanf("%d", &N);

    for (i = 0; i < N; i++) res[2 * i + 1] = ' ';    
    res[2 * N - 1] = '\\n';                           

    dpl(0);    

    return 0;
}

• 백트래킹 재귀

  dp1 함수가 각 깊이에 가능한 모든 수를 넣은다음 이미 쓴 수는 건너뛰고 N개가 되면 결과를 출력

• 중복 체크

  chk 배열로 어떤 수가 이미 사용되었는지 확인

• res 배열

  각 자리 한 번에 출력

8/11

2407번

#include <stdio.h>
#include <string.h>

char dp[105][105][1050];

void add(char *a, char *b, char *res) {
    int i, carry = 0;
    int lena = strlen(a), lenb = strlen(b);
    int len = lena > lenb ? lena : lenb;
    for (i = 0; i < len || carry; i++) {
        int digit = carry;
        if (i < lena) digit += a[lena-1-i] - '0';
        if (i < lenb) digit += b[lenb-1-i] - '0';
        res[i] = digit % 10 + '0';
        carry = digit / 10;
    }
    res[i] = 0;
    for (int j = 0; j < i/2; j++) {
        char t = res[j];
        res[j] = res[i-1-j];
        res[i-1-j] = t;
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i; j++)
            if (j == 0 || j == i) strcpy(dp[i][j], "1");
            else {
                char tmp[1050], tmp2[1050];
                add(dp[i-1][j-1], dp[i-1][j], tmp); //덧셈 결과 tmp에 저장하기
                strcpy(dp[i][j], tmp);
            }
    printf("%s\\n", dp[n][m]);
    return 0;
}