백준 2563 - 색종이 (자바, C, C++, node.js, Kotlin, Python, C#)

 문제 : boj2563

---

 

필요 알고리즘 개념

• 구현
  
  • 문제에 제시된대로 구현을 하면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  가장 쉽게 생각해볼 수 있는건, 100x100 짜리 배열을 만든 후 전부 0 또는 false로 초기화한다. 이후 입력을 받아 10X10 정사각형 모양의 색종이를 직접 배열에 +1 혹은 true로 변경한다. 이후 100x100 배열을 한번 더 순회하면서 0 또는 false가 아닌 배열 값의 수를 세면 된다. 칸이 좀 안맞긴하고, 10개씩 채운것도 아니긴 하지만 아래 이미지와 같은 식으로 배열에 체크하는 것이다. 이 경우, 입력으로 들어온 색종이의 수가 N이라 할 때, O(NRC+RC) (NRC는 입력받아 배열 채우는 것, 뒤의 RC는 배열 순회하면서 답 구하는 것) 로 구할 수 있다.

 

  조금 더 줄여본다면, 배열에 체크하면서 단 한번만 체크해주면 된다. 예를들어 색종이의 위치 r과 c를 받아서 arr[r][c]++ 를 해준다고 할 때, 해당 값이 0에서 1로 바뀐 시점에서만 체크해주면 되므로 이후 따로 순회를 안해줘도 된다. 그럼 O(NRC)가 된다.

for (int i = r; i < r+10; i++) {	// 입력으로 받은 색종이의 r 부터 r+10까지
    for (int j = c; j < c+10; j++) {	// 입력으로 받은 색종이의 c부터 c+0까지
        if (++arr[i][j] == 1)	// 100x100 배열에서 +1 를 했을 때 1이 되는 시점에
            ans++;	// 출력할 답을 +1 해준다.
    }
}

 

---

 

  풀이 자체는 그리 어렵지 않은 문제인데, 그냥 재밌을 것 같아서 중간중간 조금씩 익히고 있던 언어들 각각으로 한번 짜봤다. 차이는 아래와 같았다.

 

 

코드 (Java) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[100][100];
        int ans = 0;
        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            for (int i = r; i < r+10; i++) {
                for (int j = c; j < c+10; j++) {
                    if (++arr[i][j] == 1)
                        ans++;
                }
            }
        }
        System.out.println(ans);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드 (C) : github

#include <stdio.h>

const int RANGE = 10;
int ans = 0;
int arr[100][100] = {0,};

void increase(int r, int c) {
    for (int i = r; i < r+RANGE; i++) {
        for (int j = c; j < c+RANGE; j++) {
            if (++arr[i][j] == 1)
                ans++;
        }
    }
}

int main() {
    int arr[100][100] = {0,};
    int n, r, c;
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &r, &c);
        increase(r, c);
    }
    printf("%d", ans);
    return 0;
}

 

 

코드 (C++) : github

#include <iostream>
using namespace std;

int arr[100][100] = {0,};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, c, ans=0;
    cin >> n;
    while (n--) {
        cin >> r >> c;
        for (int i = r; i < r+10; i++) {
            for (int j = c; j < c+10; j++) {
                if (++arr[i][j] == 1)
                    ans++;
            }
        }
    }
    cout << ans;
}

 

 

코드 (파이썬) : github

import sys
input=sys.stdin.readline

arr = [[0 for _ in range(100)] for _ in range(100)]
n = int(input())
ans = 0

for _ in range(n):
    r, c = map(int, input().split())
    for i in range(r, r+10):
        for j in range(c, c+10):
            arr[i][j] += 1
            if arr[i][j] == 1:
                ans += 1

print(ans)

 

 

코드 (C#) : github

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Linq;

namespace Prac {
    class Program {
        private static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        private static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        static void Main(String[] args) {
        	int n = int.Parse(sr.ReadLine());
        	int ans = 0;
        	int[] arr = Enumerable.Repeat<int>(0, 10000).ToArray<int>();
        	while (n-->0) {
        		string[] inp = sr.ReadLine().Split(" ");
        		int r = int.Parse(inp[0]);
        		int c = int.Parse(inp[1]);
        		
        		for (int i = r; i < r+10; i++) {
        			for (int j = c; j < c+10; j++) {
        				if (++arr[i*100+j] == 1) {
        					ans++;
        				}
        			}
        		}
        	}
        	sw.Write(""+ans);
        	sw.Flush();
        }
    }
}

 

 

코드 (코틀린) : github

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = Array(100){IntArray(100){0}}
    var ans = 0
    repeat(n) {
        val st = StringTokenizer(readLine())
        val r = st.nextToken().toInt()
        val c = st.nextToken().toInt()
        for (i in 0 until 10) {
            for (j in 0 until 10) {
                if (++arr[r+i][c+j] == 1)
                    ans++
            }
        }
    }
    print(ans)
}

 

 

코드 (node.js) : github

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on("line", line => {
  input.push(line);
}).on("close", () => {
  const n = parseInt(input[0]);
  let ans = 0;
  let arr = Array.from(Array(100), () => Array(100).fill(0))
  for (t = 1; t <= n; t++) {
  	const tmp = input[t].split(" ").map(i => parseInt(i));
	let r = tmp[0];
	let c = tmp[1];
	for (i = r; i < r+10; i++) {
		for (j = c; j < c+10; j++) {
			if (++arr[i][j] == 1)
				ans++;
		}
	}
  }
  console.log(ans);

  process.exit();
});