백준 알고리즘 - 2563번 색종이 문제입니다.

(참고 - https://www.acmicpc.net/problem/2563)

코드)

#include <stdio.h>

int arr[100][100];

void put_rect(int i, int j) {

   int k, p;

   int tmp = j;

   for (k = 0; k < 10; k++) {

      j = tmp;

      for(p = 0; p < 10; p++) {

         arr[i][j] = 1;

         j++;

      }

      i++;

   }

}

int calc_rect_size()

{

   int i, j, cnt = 0;

   for(i = 0; i < 100; i++)

      for(j = 0; j < 100; j++)

         if( arr[i][j] )

            cnt++;

   return cnt;

}

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

   int i, num, tmp1, tmp2;

   scanf("%d", &num);

   for(i = 0; i < num; i++) {

      scanf("%d %d", &tmp1, &tmp2);

      put_rect(tmp1, tmp2);

   }

   printf("%d\n", calc_rect_size());

}

- 먼저 전역변수로 2차원배열 arr를 100, 100의 크기만큼 선언하여 0으로 초기화 해줍니다.

그 후 두 수(tmp1, tmp2)를 입력받아 put_rect 함수의 변수로 넘겨줍니다.

put_rect함수에서는 입력받은 두 수가 예를 들어 3, 7이라 가정하면 arr[3][7] 부터 위, 오른쪽의 방향으로 10만큼 전부 1의 값으로 바꿔줍니다.

그렇게 되면 알기쉽게 표현하면 arr[3~13][7~17]에 저장된 값들은 전부 1, 나머지는 전부 0으로 배열 arr이 저장됩니다.

이와 같은 식으로 main의 for문을 통해 입력 받는 두 수에 대하여 배열 arr의 값을 1로 바꿔줍니다.

결과적으로 calc_rect_size함수에서는 배열 arr에 저장된 값을 1인지, 0인지를 비교하여 1이라면 카운트하여 더해준 후 최종 카운트 된 값을 리턴해줍니다.

이 값이 색종이가 붙은 검은영역의 넓이라 할 수 있습니다.

백준 알고리즘 - 2525번 오븐 시계 문제입니다.

(참고 - https://www.acmicpc.net/problem/2525 )

코드)

#include <stdio.h>

int main() {

int hour, min, time;

scanf("%d %d", &hour, &min);

scanf("%d", &time);

hour += time / 60;

min += time % 60;

if(min >= 60) {

hour++;

min %= 60;

}

if(hour >= 24)

hour %= 24;

printf("%d %d\n", hour, min);

return 0;

}

- 먼저 시간과 분을 첫째 줄에 입력받고, 다음 줄에는 시간을 입력받습니다.

입력받은 시간인 time변수를 60으로 나눈 값을 hour에 더하여 줍니다. time이 60보다 크다면 그 몫인 1 혹은 그 이상의 값이 hour에 추가로 더해질 것입니다. time이 60보다 작다면 int형이므로 0의 값이 hour에 더해질 것입니다.

다음으로 time을 60으로 나눈 나머지 값을 min에 더하여 줍니다. 만약 min의 결과가 60보다 크거나 같다면 hour에 1을 더해주고, min은 60으로 나눈 나머지를 저장해줍니다.

시간 hour변수의 값이 24가 넘어간다면, hour에 24로 나눈 나머지를 저장해줍니다.

이렇게 하면 시간에 대한 계산이 완료되어 그대로 hour와 min을 출력해주면 됩니다.

백준 알고리즘 - 2506번 점수계산 문제입니다.

(참고 - https://www.acmicpc.net/problem/2506 )

코드)

#include <stdio.h>

int main() {

int arr[100];

int num, i, panel=1, sum=0, tf=0;

scanf("%d", &num);

for(i=0; i < num; i++) {

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

if(arr[i] == 1) {

if(tf == 1)

panel += 1;

sum += panel;

tf = 1;

}

else {

tf = 0;

panel = 1;

}

}

printf("%d\n", sum);

return 0;

}

- tf는 연속해서 1의 값인지를 확인하기 위한 하나의 플래그 장치로 사용되는 변수입니다.

처음, 입력받을 숫자를 num이라는 변수에 담은 후 for문을 이용하여 입력받은 num의 갯수만큼 반복하여 배열에 값을 입력받도록 합니다. 배열은 개수인 100만큼 할당하여 생성해주었습니다.

 간단하게 생각하여 입력받은 값이 1일때,  tf변수의 값을 한번 더 if문을 이용하여 비교해서 1이라면 전에 입력받은 값이 1이었다고 판단할 수 있고 0이라면 전체 입력받은 값이 0이라는 것을 알 수 있습니다.

이를 이용해 tf가 1이라면 기존의 변수 panel 에 1을 추가로 더하여 결과값 sum에 panel의 값을 더해주면 됩니다.

만약 입력받은 값이 0이라면 tf는 0으로, panel은 기본값 1로 초기화시키는 과정을 해 주면 됩니다.

백준 알고리즘 - 2501번 약수 구하기 문제입니다.

(참고 - https://www.acmicpc.net/problem/2501 )

코드 )

#include <stdio.h>

int main() {

int p, q, i, k, count=0;

int arr[BUFSIZ];

scanf("%d %d", &p, &q);

for(i = 0, k = 0; i < p; i++) {

if((p % (i+1)) == 0) {

arr[k++] = i+1;

count++;

}

}

if(count < q)

printf("0\n");

else

printf("%d\n", arr[q-1]);

return 0;

}

- 약수를 구하는 하나의 방법으로, i=1부터 차례대로 증가시켜주며 , p를 i로 나눈 나머지가 0인지 (0이면, i는 p의 약수입니다.) 비교하여 만약 약수라면, 배열 arr에 그 i의 값을 저장해주고, 약수의 갯수를 체크해주는 count라는 변수를 1 더해주게 됩니다.

for문의 수행이 끝나게 되면, arr에는 약수들의 값들이 저장되어 있을 것이고, count에는 약수의 갯수만큼 저장이 되어 있을 것입니다.

이 때, 문제에서 약수의 갯수가 q보다 적어서 q번째 약수가 존재하지 않을 때에는 0을 출력하라는 조건이 있었으므로 

if문을 이용하여 해당 케이스를 예외처리해줍니다.

그 외의 경우에는 배열arr에서 q번째(배열의 인덱스로는 q-1) 의 값을 출력해줍니다.

이와 같이 문제를 해결할 수 있습니다. 약수의 갯수를 어떻게 구하는지에 대한 알고리즘을 설계하는 것이 중점이라고 생각됩니다.

백준 알고리즘 2441번 별 찍기 문제입니다.

(참고 - https://www.acmicpc.net/problem/2441 )

C의 가장 원초적인 코딩, 별찍기 문제입니다. 

별 찍기 문제를 올릴까말까 고민하다가, 알고리즘의 기초라 생각하여 올리게 되었습니다.

백준 알고리즘 2438~2441까지 별찍기 1~4 문제이며,

알고리즘은 유사하기 때문에 저는 별 찍기 4번만 다루도록 하겠습니다.

코드 )

#include <stdio.h>

int main() {

int i, j, N;

scanf("%d", &N);

for(i=0; i<N; i++) {

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

printf(" ");

for(j=N; j>i; j--)

printf("*");

printf("\n");

}

return 0;

}

- 사실 딱히 설명할 부분이 없습니다. 알고리즘 초반부에 for문과 printf, 더하여 이중 for문을 어떻게 활용해야하는 가에 대한 고민을 필요로 하는 문제라고 생각됩니다.

어떻게보면, 고민을 해보지 않으면 상당히 귀찮은 문제라 할 수도 있겠습니다.

'알고리즘을 하려면 무엇이던지 고민해보고, 생각하라!' 라는 의미의 문제랄까요.

printf를 이용한 공백과 별을, 이중 for문을 이용하여 적절히 섞어주면 됩니다.

어려운 규칙이 아닌데다가 보시는 분의 고민하는 시간을 드리고자 따로 설명은 갖지 않겠습니다.

백준 알고리즘 - 1789번 수들의 합 문제입니다.

(참고 - https://www.acmicpc.net/problem/1789 )

코드)

#include <stdio.h>

int main() {

long long int S, i, n=0;

int cnt=0;

scanf("%lld", &S);

for(i=1; ; i++) {

n += i;

cnt++;

if(n > S) {

                        cnt--;

break;

}

}

printf("%d\n", cnt);

return 0;

}

무슨 차이가 있는지 발견하셨나요?

로직도 그대로, 변수들의 값들 또한 그대로, 

차이가 있다면 한가지 있습니다.

바로 전 알고리즘 포스팅에서 밝혔었죠. 문제를 유심히 살펴보시라는 말씀을 드렸었습니다.

바로 문제의 조건입니다. 

"첫째 줄에 자연수 S(1≤S≤4,294,967,295)가 주어진다."

그래서 S는 long long int의 값으로 해주었는데?

라고 생각을 하실지 모르겠지만, S뿐만이 아닙니다. 결과값 N을 구해주기 위해 반복문 안에서 루프 조건은

무한루프라는점 입니다. 즉 long long int타입의 S를 만나기 위해서는 i와 n 또한 기본 int형 이상의 값을 필요로 할 수 있으며, 만약 S의 최대값으로 4,294,967,295 라는 값이 입력되었다면 n은 그 이상의 수가 저장됩니다. 

if(n>S)이 이 무한 루프를 끝낼 수 있는 조건이기 때문입니다. 즉 연산과정에서 사용되는 i와 n 또한 long long int타입으로 선언되어져야 시간초과에러를 풀어낼 수 있습니다.

이 부분만 해결하면 나머지는 i를 0부터 차근차근히 더해주어 n에 저장시켜주고, n과 S를 비교하는 단순한 로직이기 때문에 설명은 이정도로 마무리 짓도록 하겠습니다.

백준 알고리즘 1731번 추론문제입니다.

(참고 - https://www.acmicpc.net/problem/1731 )

코드)

#include <stdio.h>

int arr[50], temp[50], temp2[50];

int main() {

int N, i;

scanf("%d", &N);

for(i=0; i<N; i++) {

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

}

for(i=0; i<N; i++) {

temp[i] = arr[i+1] - arr[i];

temp2[i] = arr[i+1] / arr[i];

}

for(i=0; i<N; i++) {

if(temp[i] == temp[i+1]) { //등차

printf("%d\n", arr[N-1]+temp[0]);

break;

}

if(temp2[i] == temp2[i+1]) { //등비

printf("%d\n", arr[N-1]*temp2[0]);

break;

}

}

return 0;

}

- 백준 알고리즘 문제들은 항상 느끼는 것이지만, 문제를 제대로 읽지 않으면 시간초과 혹은 틀렸습니다. 를 접하게 되는것같습니다. 반드시 문제에서 주는 조건들을 유심히보시고 소홀히 하지 않으시기 바랍니다.

이번 문제는 첫째 줄에 입력받을 N의 갯수가 0~50으로 제한됩니다. 따라서 배열의 크기는 50이상으로 잡아주어야 합니다.

이후 arr배열에 값들을 입력받아 저장하도록 하고, temp라는 배열에는 등차수열의 공식을 적용하고 temp2라는 배열에는 등비수열의 공식을 적용하여 각각 저장해줍니다. 그 후, if문을 두 가지 케이스로 넣어서 arr에 저장되어있는 값이 등차인지 등비인지를 구분하도록 나눠주었습니다.

두 케이스를 나눠 준 뒤, 

만약 등차라면 기존 arr[N-1]에 저장된 마지막 값에 공차값(temp[0])을 더해줌으로써 다음 값을 도출해낼 수 있고,

등비라면 arr[N-1]에 저장된 마지막 값에 공비값(temp2[0])을 곱해줌으로써 다음 값을 도출합니다.

백준 알고리즘 1110번 더하기 사이클 문제입니다.

(참고 - https://www.acmicpc.net/problem/1110 )

코드)

#include <stdio.h>

int main() {

int buf[2];

int num, first, second, sum, cnt=0;

scanf("%d", &num);

if(num >= 10) {

first = num / 10;

second = num % 10;

}

else {

first = 0;

second = num;

}

buf[0] = first;

buf[1] = second;

do {

sum = 0;

sum = first + second;

first = second;

if(sum >= 10) 

second = sum % 10;

else 

second = sum;

cnt++;

} while(buf[0] != first || buf[1] != second);

printf("%d\n", cnt);

return 0;

}

- 저는 원래의 숫자를 기억하기 위해 buf라는 배열에 첫번째, 두번째 숫자를 입력하여 저장하였습니다.

0부터 99까지이므로 first는 입력받은 숫자를 10으로 나눠주어 몫의 값을, second에는 10으로 나눈 나머지의 값을 하여 0~9의 숫자가 각각 들어가게 됩니다. 이후 do-while문을 이용하여 처음 한번은 무조건 수행하는 로직으로, 

buf[0](== 초기 입력받은 first값)과 buf[1](== 초기 입력받은 second값)이 로직에 의해 변한 first값과 second이 하나라도 다를동안은 계속 반복하도록 하였으며, sum이라는 임시 변수를 하나 두어, while문 안에서 first와 second의 값을 계속 변화시켜주도록 하였습니다.

이 또한 문제를 보시고 '더해줄 때의 뒤의 숫자가, 계산 후의 10의자리로 변한다' 라는 규칙을 찾으면 되는 부분입니다.

+Java)

import java.util.Scanner;

public class algo1110 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int ori = sc.nextInt();

int[] split = new int[2];

split[0] = ori / 10;

split[1] = ori % 10;

int flag = 1;

move(split);

while(true) {

if(ori == calc(split)) {

System.out.println(flag);

break;

} else {

move(split);

flag++;

}

}

sc.close();

}

public static void move(int[] arr) {

int tmp = arr[1];

arr[1] = (arr[0] + arr[1]) % 10;

arr[0] = tmp;

}

public static int calc(int[] arr) {

return (arr[0] * 10) + arr[1];

}

}