구간 합을 구할 때 사용되는 알고리즘으로 배열의 길이가 짧은 경우 이중 for문을 사용해서 구하면 되지만
배열의 길이가 길어지면 시간 초과가 발생하므로 투 포인터 알고리즘을 사용한다.
아래 코드에서 보면 N은 배열의 크기, M은 구하고자 하는 합이다.
구간의 합이 M을 만족하는 경우의 수를 구한다고 하자.
start, end 모두 배열의 첫번째부터 시작한다.
- M = sum
구간의 합이 M과 같다면 경우의 수 total에 1을 추가한다.
그리고 end를 한칸 뒤로 움직인다.
- M < sum
현재 구간의 합이 구하고자 하는 구간의 합보다 크다면 start를 1씩 증가시켜 주면서 구간의 범위를 좁혀준다.
이 때 start가 end보다 커지게 되는 경우 start, end를 같은 위치로 처리한다.
- M > sum
현재 구간의 합이 구하고자 하는 구간의 합보다 작다면 end를 한칸 뒤로 움직여 구간의 범위를 넓혀준다.
[코드]
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];
}
}
하지만 시간 제한이 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;
}
