십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.
아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.
십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.
크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.
입력
첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.
접근 방법
첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때,
모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다.
처음에는,
십자가 중심 2개를 (r1, c1), (r2, c2) 라고 했을 때, DFS를 이용하여 모든 (r1, c1), (r2, c2) 의 조합을 구했다.
그 후, 십자가 두개의 크기를 각각 1씩 증가시켜 나가면서 넓이를 구했다.
그러나 이 방식은 완전탐색이 아니다.
왜냐하면 1번 십자가의 크기를 1 증가시킨 후 -> 1번과 2번 십자가가 겹치지 않는 한에서 2번 십자가의 크기를 1 증가한 뒤 넓이를 계산했기 때문이다. 완전탐색을 하려면 반대 순으로도 넓이를 각 경우에 대해 계산해야하며, 중간에도 계산을 한번 더 해야한다.
즉, 아래와 같이 여러번의 계산이 필요한 것이다.
1번 십자가 크기 1 증가 -> 넓이 계산 -> 2번 십자가 크기 1 증가 -> 넓이 계산 2번 십자가 크기 1 증가 -> 넓이 계산 -> 1번 십자가 크기 1 증가 -> 넓이 계산
또한, 아래 링크의 테스트케이스는 4달 전에 추가된 데이터로, 이 경우도 주의해야한다.
이렇게 두가지 고려할 점이 있지만
첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때, 모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다.
이 방식으로 그냥 모든 가능한 경우를 완전탐색하면 보다 단순하게 해결 가능하다.
#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
int N, M;
char map[15][15];
int answer = 0;
//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
//(r,c)가 중심일 때, 가능한 십자가의 최대 크기
int getSize(int r, int c){
int ret = 0;
while(1){
bool flag = true;
for(int i = 0; i<4; i++){
int nr = r + dr[i]*ret;
int nc = c + dc[i]*ret;
if(nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc] != '#'){
flag = false;
break;
}
}
if(flag) ret++;
else break;
}
return ret - 1; //ret가 0부터 시작하므로, 처음 통과하면 ret=1이 되는데 이때 십자가의 크기는 0임 ('*' 한개짜리)
}
//중심이 (r,c)이고 크기가 K인 십자가를 만들거나(val='#') 십자가 원상복구(val='.')
void make_cross(int r, int c, int k, int val){
for(int i = 0; i<=k; i++){
for(int j = 0; j<4; j++){
int nr = r + dr[j]*i;
int nc = c + dc[j]*i;
map[nr][nc] = val;
}
}
}
int main()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> map[i][j];
}
}
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
if(map[i][j] == '#'){
int step1 = getSize(i,j);
for (int k = 0; k <= step1; k++) //첫번째 십자가 크기 1부터 max까지,
{
make_cross(i,j,k,'*'); //첫번째 십자가 표시
for(int r = 0; r<N; r++){
for(int c=0; c<M; c++){
if(map[r][c] == '#'){
int step2 = getSize(r,c); //각 크기에 대해 두번째 십자가 크기 구하기
int width1 = 4*k + 1;
int width2 = 4*step2 + 1;
answer = max(answer, width1*width2);
}
}
}
make_cross(i,j, k, '#'); //첫번째 십자가 원상복구
}
}
}
}
cout << answer;
return 0;
}
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
가로
세로
대각선
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.
접근 방법
DFS를 활용한 재귀로 완전탐색을 해 준다.
dr[], dc[]에 가로, 세로, 대각선 방향의 수를 저장하고 for()문에서 가로,세로,대각선을 반복하면서 파이프의 끝 위치를 옮긴다.
이때, 가능한 조합 중, "가로->세로 "와 "세로->가로"는 이동할 수 없는 조합이므로, 이를 제외한다.
또한 주의할 점은 대각선일 때이다.
아래의 그림처럼 파이프의 끝이 (2,3) -> (3,4)로 이동하는 경우에, (3,4)뿐만 아니라 (2,4)와 (3,3)도 모두 벽이 아니어야 이동할 수 있기 때문에 이 두개 중 벽이 하나라도 있는 경우는 제외한다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워크 주소’와 ‘네트워크 마스크’라는 두 개의 정보로 표현된다.
IP 주소는 네 개의 바이트로 구성되어 있으며, 각각을 10진수로 나타내고(앞에 0을 붙이지 않은 형태로) 사이에 점을 찍어 주소를 표현한다. 바이트이기 때문에 각각의 수는 0부터 255까지의 값을 갖게 된다. 네트워크 주소와 네트워크 마스크 역시 같은 형식으로 나타낸다.
IP 네트워크에 대해 올바르게 이해하기 위해서는 위와 같은 주소를 2진수로 이해하면 된다. 즉, 각각의 바이트를 8자리의 이진수로 나타내고, 이를 네 개 붙여놓은(앞에서부터) 32자리의 이진수를 생각해 보자. IP 네트워크에는 기본적으로 2m개의 컴퓨터(혹은 IP 주소)가 할당될 수 있다. 이 경우의 네트워크 주소는 앞의 32-m 자리가 임의의 수(0 또는 1)로 구성되어 있고, 뒤의 m자리는 0으로 채워지게 된다. 네트워크 마스크는 앞의 32-m 자리가 1로 채워져 있고, 뒤의 m자리는 0으로 채워지게 된다. 이와 같은 IP 네트워크에는 앞의 32-m 자리가 네트워크 주소와 일치하는 모든 IP들이 포함되게 된다.
예를 들어 네트워크 주소가 194.85.160.176이고, 네트워크 마스크가 255.255.255.248인 경우를 생각해 보자. 이 경우, 이 네트워크에는 194.85.160.176부터 194.85.160.183까지의 8개의 IP 주소가 포함된다.
어떤 네트워크에 속해있는 IP 주소들이 주어졌을 때, 네트워크 주소와 네트워크 마스크를 구해내는 프로그램을 작성하시오. 답이 여러 개인 경우에는 가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.
입력
첫째 줄에 정수 n(1≤n≤1,000)이 주어진다. 다음 n개의 줄에는 각 컴퓨터의 IP 주소가 주어진다.
출력
첫째 줄에 네트워크 주소를, 둘째 줄에 네트워크 마스크를 출력한다.
접근 방법
1) 입력받은 각 ip 주소를 의미하는 문자열을 '.'를 기준으로 split 하여 inputIp[]에 넣는다. 다음 바이트 자리 숫자를 입력받을때는, 먼저 왼쪽으로 8비트를 shift한 뒤에 입력받은 숫자를 or 연산을 이용하여 inputIp[]를 갱신한다.
세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.
세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.
출력
첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.
접근 방법
substr()함수를 이용해서 풀 수 있는 간단한 문자열 비교 문제였다. 그런데 생각보다 정답률이 낮아서 의아했는데 문제를 풀어보니 주의할 점을 고려해주지 않으면 오답처리되기 쉽다는 것을 알 수 있었다. 문제 조건을 꼼꼼히 확인하는것이 중요하다는 것을 새삼 깨달을 수 있게 해주는 문제였다. 주의할 점은 다음과 같이 두 개 정도 있다.
주의할 점 1)
문서의 길이가 단어 길이보다 작은 경우에는 예외 처리를 따로 해줘야 한다. 이 부분을 고려해주지 않아서 런타임 에러가 났다.
주의할 점 2)
일치하는 문자열을 찾은 뒤, 중복되지 않도록 단어의 길이만큼 문서를 스킵하기 위해 인덱스를 임의로 조정해주는데,
