하지만 시간 제한이 0.5초인데 M의 범위가 1부터 3억이라서 이중 for문을 사용하면 시간초과가 발생한다.
따라서 구간합 구하는 알고리즘인 투 포인터 알고리즘을 사용해서 풀었다.
start , end 를 배열의 첫번째 index부터 시작해서
현재 구간 합이 M보다 작으면 end를 +1, M보다 크면 start를 +1
이런 방식으로 start, end 의 index를 조절하면서 구간 합을 구했다.
[코드]
시간 : 0ms
#include <iostream>
#define MAX 10000
using namespace std;
int N,M;
int arr[MAX];
int main(void)
{
int total=0;
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++) scanf("%d",&arr[i]);
int start =0 ;
int end =0;
int sum =arr[0];
while(start <= end && end < N)
{
if(sum < M) sum += arr[++end];
else if( sum > M)
{
sum -= arr[start++];
if( start > end && start <N){
end= start;
sum= arr[start];
}
}
else if (sum == M)
{
total++;
sum += arr[++end];
}
}
printf("%d",total);
return 0;
}
한 칸에 여러 말이 쌓여 있을 수 있고 이동하려는 말 위에 다른 말이 존재한다면 같이 움직인다.
한 칸에 말이 4마리 이상 쌓일 경우 게임이 종료된다.
이동하려는 칸이 흰색인 경우 이동하려는 말의 위에 있는 말부터 쌓이기 시작한다.
이동하려는 칸이 빨간색일 경우 이동하려는 말부터 쌓이기 시작한다.
이동하려는 칸이 파란색일 경우 반대 방향으로 바꾸고 움직인다.
방향을 바꿔도 파란색이라면 움직이지 않는다.
범위를 벗어나는 경우도 파란색의 경우와 동일하게 한다.
solve 함수에서 1번 말부터 움직이고
이동하려는 칸의 색깔에 알맞게 white, red, blue에 맞는 함수를 호출했다.
blue인 경우 방향을 바꾸고 움직여야 하므로 동일하게 move 함수를 호출한다.
red , white의 경우 말이 움직이는 순서만 다를 뿐 다른 것은 같으므로
move 함수 하나로 처리하고 말이 쌓일 때만 white인지 red 인지 구분하여 쌓이는 순서를 다르게 해줬다.
[코드]
시간 : 0ms
#include <iostream>
#include <vector>
#define MAX 12
using namespace std;
int N,K;
int color[MAX][MAX]={0,};
vector<int> map[MAX][MAX];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
struct HORSE{
int x,y,dir;
};
HORSE horse[10];
bool move(int col , int idx)
{
int x = horse[idx].x;
int y = horse[idx].y;
int dir = horse[idx].dir;
int nx = x+dx[dir];
int ny = y+dy[dir];
vector<int> v;
int _size = map[x][y].size();
while(1)
{
int num = map[x][y][_size-1];
_size--;
map[x][y].pop_back();
v.push_back(num);
if(num==idx) break;
}
if(col ==0){
for(int i=v.size()-1;i>=0;i--)
{
int num = v[i];
map[nx][ny].push_back(num);
horse[num].x= nx;
horse[num].y = ny;
}
}
else {
for(int i=0;i<v.size();i++)
{
int num = v[i];
map[nx][ny].push_back(num);
horse[num].x= nx;
horse[num].y = ny;
}
}
if(map[nx][ny].size() >= 4) return false;
return true;
}
bool blue(int idx)
{
bool res = true;
int x = horse[idx].x;
int y = horse[idx].y;
int dir = horse[idx].dir;
int nx = x+dx[dir];
int ny = y+dy[dir];
if(nx< 0 || ny < 0 || nx >= N || ny >= N || color[nx][ny]==2) return true;
else if(color[nx][ny]==0) res = move(0,idx);
else if(color[nx][ny]==1) res = move(1,idx);
return res;
}
bool solve()
{
for(int i=0;i<K;i++){
bool res=true;
int x = horse[i].x;
int y = horse[i].y;
int dir = horse[i].dir;
int nx = x+dx[dir];
int ny = y+dy[dir];
if(nx< 0 || ny < 0 || nx >= N || ny >= N || color[nx][ny]==2){
if(dir ==0) horse[i].dir=1;
else if(dir ==1) horse[i].dir=0;
else if(dir ==2) horse[i].dir=3;
else if(dir ==3) horse[i].dir=2;
res = blue(i);
}
else if(color[nx][ny]==0) res = move(0,i);
else if(color[nx][ny]==1) res = move(1,i);
if(res==false) return false;
}
return true;
}
int main(void)
{
scanf("%d %d",&N,&K);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
scanf("%d",&color[i][j]);
}
}
for(int i=0;i<K;i++){
int x,y,dir;
scanf("%d %d %d",&x,&y,&dir);
horse[i] = {x-1,y-1,dir-1};
map[x-1][y-1].push_back(i);
}
int turn=0;
while(1){
turn++;
if(!solve()) break;
else if(turn > 1000){
printf("-1");
return 0;
}
}
printf("%d",turn);
return 0;
}
시뮬레이션 문제로 낚시하는 함수인 fishing과 물고기가 이동하는 함수인 move를 구현하여 풀었다.
물고기들의 정보를 구조체에 저장하여 1번 물고기부터 M번 물고기까지 차례대로 이동
이 때, 한 칸에는 한 마리의 물고기만 존재할 수 있으므로 visited 배열을 사용해 처리한다.
(자신보다 큰 물고기가 있을 경우 죽도록)
[코드]
시간 : 44ms
#include <iostream>
#define MAX 101
using namespace std;
struct FISH{
int x,y,s,d,z;
bool die;
};
int R,C,M;
int score=0;
int map[MAX][MAX]={0,};
FISH fish[MAX*MAX];
int idx =0;
int dx[5] = {0,-1,1,0,0};
int dy[5] = {0,0,0,1,-1};
void move()
{
int visited[MAX][MAX]={0,};
for(int i=1;i<=M;i++){
if(fish[i].die) continue;
int dir = fish[i].d;
int x = fish[i].x;
int y = fish[i].y;
int s = fish[i].s;
int nx;
int ny;
while(1){
nx = x+ dx[dir] * s;
ny = y+ dy[dir] * s;
if( nx >=1 && ny >=1 && nx <= R && ny <= C) break;
else if ( dir == 1 ) {
s = s - (x-1);
x = 1;
dir = 2;
}
else if ( dir == 2 ) {
s = s - (R-x);
x = R;
dir =1;
}
else if ( dir == 3 ) {
s = s - (C-y);
y = C;
dir = 4;
}
else if ( dir == 4 ) {
s = s- (y-1);
y =1;
dir= 3;
}
fish[i].d = dir;
}
fish[i].x = nx;
fish[i].y = ny;
if(visited[nx][ny] != 0)
{
int num = visited[nx][ny];
if( fish[i].z < fish[num].z) fish[i].die = true;
else{
visited[nx][ny]=i;
fish[num].die = true;
}
}
else visited[nx][ny]=i;
}
for(int i=1;i<=R;i++){
for(int j=1;j<=C;j++) map[i][j] = visited[i][j];
}
}
void fishing(int idx)
{
for(int i=1;i<=R;i++)
{
if(map[i][idx] != 0){
int num= map[i][idx];
score+=fish[num].z;
map[i][idx]=0;
fish[num].die=true;
return;
}
}
}
int main(void)
{
scanf("%d %d %d",&R,&C,&M);
for(int i=1;i<=M;i++){
int x,y,s,d,z;
scanf("%d %d %d %d %d",&x,&y,&s,&d,&z);
map[x][y]=i;
fish[i] = {x,y,s,d,z,false};
}
for(int i=1;i<=C;i++){
fishing(i);
move();
}
printf("%d",score);
return 0;
}