ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.
문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.
그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림
방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.
손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다. 같은 이유로 102 호보다 2101 호를 더 선호한다.
여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다.
입력
프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W).
출력
프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행을 출력하는데, 내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.
예제 입력 1
2
6 12 10
30 50 72
예제 출력 1
402
1203
C++ Code
#include <iostream>
using namespace std;
int main()
{
int t, h, w, n, ah, aw;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
scanf("%d %d %d", &h, &w, &n);
ah = n%h == 0 ? h : n%h;
aw = n/h;
aw = n - aw*h > 0 ? aw+1 : aw;
printf("%d\n", ah*100 + aw);
}
return 0;
}
만약 글을 읽는 도중, 어렵거나 이해가 되지 않는 부분이 있다면 댓글을 달아주시기 바랍니다.
CPU 구조
CPU는 크게 3가지로 나누어 집니다. 연산 장치, 제어 장치, 레지스터가 그것입니다. 먼저 연산 장치와 레지스터를 알아보겠습니다.
– 연산 장치 덧셈과 같은 산술 연산과 논리곱(and), 논리합(or), 부정(!) 등의 논리 연산을 수행합니다. 연산 장치는 연산에 필요한 데이터를 레지스터에서 가져오고, 연산 결과를 다시 레지스터로 보내 저장합니다.
– 레지스터 명령어 주소, 명령어 코드, 연산에 필요한 데이터, 연산 결과 등을 임시로 저장합니다. CPU 처리 속도와 비슷한 고속 기억장치입니다.
– 제어 장치 명령어를 순서대로 실행할 수 있도록 제어하는 장치입니다. 메모리에서 명령어를 꺼내 해독한 후, 명령어 실행에 필요한 제어 신호를 해당하는 장치로 보내 정확하게 수행할 수 있도록 지시합니다. 장치로는 제일 먼저 CPU의 연산 장치, 프린터, 키보드, 모니터 등이 있습니다.
다음으로 CPU 물리적 구조 중, 소켓과 코어에 대해 소개합니다.
– 소켓 CPU를 받아들이는 서버(컴퓨터)의 메인보드의 접촉부입니다. 즉, 소켓이 2개라면 CPU 를 2개 까지 장착 가능합니다.
– 코어 실제 CPU 역할을 수행하는 구성 요소입니다. 코어 개수가 많을수록, 동시에 처리 가능한 명령문의 수가 늘어나게 됩니다. Hyper Threading 기능을 사용한다면 코어당 2개, 사용하지 않는다면 1개의 명령문을 동시에 수행 가능합니다.
CPU 동작 원리
– CPU 동작 순서 제어 장치가 메모리에서 명령어를 꺼내 해독 -> 명령어 수행에 필요한 제어 신호를 연산 장치로 전달 -> 산술논리연산 처리(계산 시 임시 저장은 레지스터에서 처리) -> 메모리로 결과값 전달(혹은 출력 장치로 전달)
– CPU 클럭 CPU를 비롯한 모든 컴퓨터 부품들은 일정한 간격으로 발생하는 전기적 신호, 즉 클럭에 맞추어 동작합니다. 클럭이 발생하고 바로 다음 클럭이 발생할 때 까지의 간격을 사이클이라고 하며, 이것을 표기할 때 Hz로 표기합니다.
– 명령 주기 명령 주기는 크게 4가지로 분류됩니다. 각 주기 별 소요 사이클(클럭)은 N개 이며 각 CPU 마다 다릅니다.
I. 명령어 패치(fetch) 명령어의 명령 코드(Opcode) 부분을 명령 레지스터에 저장합니다.
II. 명령어 디코딩 fetch 된 Opcode 는 다음 단계를 위해 해독(디코딩)되어 적절한 레지스터로 이동됩니다.
III. Operand 유효한 주소 읽기 Operand 가 direct address 인 경우 다음 단계로 진행, Operand 가 indirect address 인 경우 유효 주소를 계산해 메모리로 부터 읽어들입니다.
IV. 명령 실행 해독된 정보와 Operand 를 통해 명령을 수행하여 주기억장치에(메모리) 결과를 저장하거나 출력장치로 전달합니다.
– IPC (Instructions Per Cycle) 한 클럭 당 처리할 수 있는 명령어 수를 말합니다. CPU 모델 마다 명령 주기에 필요한 클럭 수는 다르며 공식적인 수치는 제공되지 않습니다.
CPU 성능 = (클럭 * IPC) * 코어 수(or 스레드 수)
CPU Ready 란?
프로세스가 새롭게 생성되면 Ready Queue 에 들어가 실행되기를 대기합니다. 이 대기하는 상태를 Ready 상태라고 합니다. 프로세스란 쉽게 말해, 실행 상태인 프로그램을 의미합니다.
Ready 상태인 프로세스는 자신의 순서가 되면 CPU 스케줄러에 의해 동작하게 됩니다. 이렇게 실행되고 있는 상태를 Running 상태라고 합니다.
Running 상태인 프로세스는 할당된 시간이 초과되면 Interrupt 에 의해 자원을 반환하고 다시 Ready 상태가 됩니다. 이렇게 Interrupt 가 발생하는 이유는, 특정 프로세스 들의 자원 독점으로 인해 무한정 Ready 상태로 기다려야하는 프로세스가 발생하지 않게끔 하기 위해서입니다.
CPU Wait 이란?
다음은 CPU Wait 입니다. 프로세스가 Running 상태에서 I/O 작업을 만나면 Waiting 상태가 됩니다. 여기서 I/O 작업이라 함은 하드디스크, NAS 등과 같은 다른 장치와의 통신을통해 이루어지는 작업을 뜻합니다. I/O 작업으로 인해 Wait 상태가 되면 해당 CPU 코어는 쉬게 됩니다.
CPU Ready 와 Wait 은 아래 그림 하나로 요약할 수 있습니다.
CPU Load 란?
CPU Load 란 CPU 에 실행 중이거나 Ready 상태인 프로세스의 개수를 평균으로 보여주는 값입니다. 예를 들어 100번 확인했을 때, 113개가 있었다면 CPU Load 는 1.13으로 표시됩니다. CPU Load 임계치는 코어에 비례하며 CPU 코어가 2개라면, CPU에 항상 실행 중인 작업만 있고 두코어가 쉬지 않고 처리했을 떄 CPU Load 값은 2가 됩니다. 같은 방식으로 CPU 코어가 4개라면 4, 8개라면 8이 됩니다.
– CPU Load 임계값 일반적으로 CPU Load 임계 값은 코어가 1개일 경우 0.7로 설정합니다. 그 이유는 Load 수치는 평균으로 계산되기 때문입니다. 아래 예시를 통해 확인해 보겠습니다.
– 예시 전체 코어 : 1개 실행&Ready 상태인 프로세스 수가 0인 경우 : 20초 실행&Ready 상태인 프로세스 수가 1인 경우 : 60초 실행&Ready 상태인 프로세스 수가 2인 경우 : 20초 100초 간 CPU Load : 1 CPU 성능 저하가 있던 시간 : 20초
– 결론 따라서 CPU Load 가 코어당 0.7 정도의 수치라면 대기 중인 프로세스가 없는 원활한 상태라고 판단할 수 있습니다. 하지만 이는 일반적 시나리오일 경우이며, 실제 운영 면에서는 적절한 수치를 확인할 필요가 있습니다.
지금까지 CPU 에 대해 전체적으로 파헤쳐 보았습니다. 이글이 누군가에게 도움이 되기를 바라며 포스팅을 마치겠습니다. 긴 글 읽어주셔서 감사합니다.
# network interface create -vserver google -lif google_V2005_Data2 -role data -data-protocol nfs,cifs,fcache -address 8.8.8.9 -netmask 255.255.255.0 -home-node fas8300-node2 -home-port a0a-2005
Export-policy 생성 # export-policy create -vserver <SVM_name> -policyname <policy_name>
– 예시 : export-policy create -vserver google -policyname google_V2005
Export-policy rule 생성 # export-policy rule create -vserver <SVM_name> -policyname <policy_name> -clientmatch <IP_Addr>/<mask> -rorule any -rwrule any -superuser any -protocol any
– 예시 : export-policy rule create -vserver google -policyname google_V2005 -clientmatch 8.8.8.0/24 -rorule any -rwrule any -superuser any -protocol any
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
#include <iostream>
#include <deque>
using namespace std;
typedef struct _node
{
char h, x, y;
_node(char h, char x, char y) : h(h), x(x), y(y) {};
} tomato_node;
char tomato[101][101][101];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
char row, col, height, h, x, y;
int for_size, tomato_cnt = 0, ripe = 0, ans = -1;
deque <tomato_node> q;
cin >> for_size;
col = for_size;
cin >> for_size;
row = for_size;
cin >> for_size;
height = for_size;
for (char i = height; i > NULL; i--)
{
for (char j = 1; j <= row; j++)
{
for (char k = 1; k <= col; k++)
{
cin >> tomato[i][j][k];
if (tomato[i][j][k] == '-')
cin >> x;
else
{
tomato_cnt++;
if (tomato[i][j][k] == '1')
{
ripe++;
q.emplace_back(i, j, k);
}
}
}
}
}
for_size = q.size();
while (for_size)
{
ans++;
for (int i = 0; i < for_size; i++)
{
h = q[0].h;
x = q[0].x;
y = q[0].y;
q.pop_front();
if (h > 1 && tomato[h-1][x][y] == '0')
{
tomato[h-1][x][y] = 1;
ripe++;
q.emplace_back(h-1, x, y);
}
if (h < height && tomato[h+1][x][y] == '0')
{
tomato[h+1][x][y] = 1;
ripe++;
q.emplace_back(h+1, x, y);
}
if (x > 1 && tomato[h][x-1][y] == '0')
{
tomato[h][x-1][y] = 1;
ripe++;
q.emplace_back(h, x-1, y);
}
if (x < row && tomato[h][x+1][y] == '0')
{
tomato[h][x+1][y] = 1;
ripe++;
q.emplace_back(h, x+1, y);
}
if (y > 1 && tomato[h][x][y-1] == '0')
{
tomato[h][x][y-1] = 1;
ripe++;
q.emplace_back(h, x, y-1);
}
if (y < col && tomato[h][x][y+1] == '0')
{
tomato[h][x][y+1] = 1;
ripe++;
q.emplace_back(h, x, y+1);
}
}
for_size = q.size();
}
if (ripe == tomato_cnt)
cout << ans;
else
cout << "-1";
return 0;
}
Python3 Code
import sys
from collections import deque
q = deque()
ripe = 0
tomato_cnt = 0
ans = -1
col, row, height = map(int, sys.stdin.readline().rstrip().split())
tomato = [ [] for i in range(height) ]
for i in range(height):
for j in range (row):
tomato[i].append(list(map(int, sys.stdin.readline().rstrip().split())))
for k in range (col):
if tomato[i][j][k] != -1:
tomato_cnt += 1
if tomato[i][j][k] == 1:
ripe += 1
q.append([i, j, k])
for_size = len(q)
while for_size > 0:
ans += 1
for i in range(for_size):
h = q[0][0]
x = q[0][1]
y = q[0][2]
q.popleft()
if h > 0 and tomato[h-1][x][y] == 0:
ripe += 1
tomato[h-1][x][y] = 1
q.append([h-1, x, y])
if h < height-1 and tomato[h+1][x][y] == 0:
ripe += 1
tomato[h+1][x][y] = 1
q.append([h+1, x, y])
if x > 0 and tomato[h][x-1][y] == 0:
ripe += 1
tomato[h][x-1][y] = 1
q.append([h, x-1, y])
if x < row-1 and tomato[h][x+1][y] == 0:
ripe += 1
tomato[h][x+1][y] = 1
q.append([h, x+1, y])
if y > 0 and tomato[h][x][y-1] == 0:
ripe += 1
tomato[h][x][y-1] = 1
q.append([h, x, y-1])
if y < col-1 and tomato[h][x][y+1] == 0:
ripe += 1
tomato[h][x][y+1] = 1
q.append([h, x, y+1])
for_size = len(q)
if tomato_cnt == ripe:
print(ans)
else:
print(-1)
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
#include <iostream>
#include <deque>
using namespace std;
int tomato[1001][1001];
deque < pair<int, int> > q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int row, col, tomato_cnt = 0, ripe = 0, for_size, x, y, ans = -1;
pair <int, int> q_elem;
cin >> col >> row;
for (int i = 1; i <= row; i++)
{
for (int j = 1; j <= col; j++)
{
cin >> tomato[i][j];
if (tomato[i][j] != -1)
{
tomato_cnt++;
if (tomato[i][j] == 1)
{
ripe++;
q.emplace_back(i, j);
}
}
}
}
for_size = q.size();
while (for_size)
{
ans++;
for (int i = 0; i < for_size; i++)
{
q_elem = q[0];
x = q_elem.first;
y = q_elem.second;
q.pop_front();
if (x > 1 && tomato[x-1][y] == 0)
{
ripe++;
tomato[x-1][y] = 1;
q.emplace_back(x-1, y);
}
if (x < row && tomato[x+1][y] == 0)
{
ripe++;
tomato[x+1][y] = 1;
q.emplace_back(x+1, y);
}
if (y > 1 && tomato[x][y-1] == 0)
{
ripe++;
tomato[x][y-1] = 1;
q.emplace_back(x, y-1);
}
if (y < col && tomato[x][y+1] == 0)
{
ripe++;
tomato[x][y+1] = 1;
q.emplace_back(x, y+1);
}
}
for_size = q.size();
}
if (tomato_cnt == ripe)
cout << ans;
else
cout << -1;
return 0;
}
Python3 Code
import sys
from collections import deque
q = deque()
ripe = 0
tomato_cnt = 0
ans = -1
col, row = map(int, sys.stdin.readline().rstrip().split())
tomato = []
for i in range (row):
tomato.append(list(map(int, sys.stdin.readline().rstrip().split())))
for j in range (col):
if tomato[i][j] != -1:
tomato_cnt += 1
if tomato[i][j] == 1:
ripe += 1
q.append([i, j])
for_size = len(q)
while for_size > 0:
ans += 1
for i in range(for_size):
x = q[0][0]
y = q[0][1]
q.popleft()
if x > 0 and tomato[x-1][y] == 0:
ripe += 1
tomato[x-1][y] = 1
q.append([x-1, y])
if x < row-1 and tomato[x+1][y] == 0:
ripe += 1
tomato[x+1][y] = 1
q.append([x+1, y])
if y > 0 and tomato[x][y-1] == 0:
ripe += 1
tomato[x][y-1] = 1
q.append([x, y-1])
if y < col-1 and tomato[x][y+1] == 0:
ripe += 1
tomato[x][y+1] = 1
q.append([x, y+1])
for_size = len(q)
if tomato_cnt == ripe:
print(ans)
else:
print(-1)
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Example 3:
Input: m = 7, n = 3
Output: 28
Example 4:
Input: m = 3, n = 3
Output: 6
Constraints:
1 <= m, n <= 100
It’s guaranteed that the answer will be less than or equal to 2 * 109.
C++Code
class Solution {
public:
int uniquePaths(int m, int n) {
vector < vector<int> > matrix(m, vector<int>(n, 1));
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
matrix[i][j] = matrix[i][j-1] + matrix[i-1][j];
}
return matrix[m-1][n-1];
}
};
Python3 Code
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
matrix = [[1 for i in range(n)] for j in range(m)]
for i in range(1, m):
for j in range(1, n):
matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
return matrix[m-1][n-1]
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.
(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.
두 정수 N과 F가 주어진다. 지민이는 정수 N의 가장 뒤 두 자리를 적절히 바꿔서 N을 F로 나누어 떨어지게 만들려고 한다. 만약 가능한 것이 여러 가지이면, 뒤 두 자리를 가능하면 작게 만들려고 한다.
예를 들어, N=275이고, F=5이면, 답은 00이다. 200이 5로 나누어 떨어지기 때문이다. N=1021이고, F=11이면, 정답은 01인데, 1001이 11로 나누어 떨어지기 때문이다.
입력
첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. F는 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 마지막 두 자리를 모두 출력한다. 한자리이면 앞에 0을 추가해서 두 자리로 만들어야 한다.
예제 입력 1
1000
3
예제 출력 1
02
C++ Code
#include <iostream>
using namespace std;
int main()
{
int n, f, mod, h, ans;
scanf("%d %d", &n, &f);
h = n/100;
mod = n % f;
if ((n - mod)/100 == h)
n -= mod;
else
n += (f-mod);
while ((n-f)/100 == h)
n -= f;
ans = n % 100;
if (ans < 10)
printf("0");
printf("%d", ans);
return 0;
}
Developer Lee 