이모티콘
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 2742 | 925 | 636 | 31.689% |
문제
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
출력
첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.
예제 입력 1
1
2
예제 출력 1
1
2
예제 입력 2
1
4
예제 출력 2
1
4
예제 입력 3
1
6
예제 출력 3
1
5
예제 입력 4
1
18
예제 출력 4
1
8
풀이
메모리랑 시간 실화냥,,?
다시 풀어야겠다 ㅠㅠ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <queue>
#include <utility>
#define p pair<int,int>
#define pi pair<p,int>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int n,result;
int ch[10000][10000];
void bfs(){
queue <pi> q; //화면, 클립보드, 카운트
q.push(pi(p(1,0),0));
ch[1][0]=1;
while(!q.empty()){
int h=q.front().first.first;
int c=q.front().first.second;
int cnt=q.front().second;
q.pop();
if(h==n){
cout << cnt << '\n';
return ;
}
if(h>=0 &&ch[h][h]==0){
q.push(pi(p(h,h),cnt+1)); //1 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
ch[h][h]=1;
}
if(h+c>=0 && c>=0 && ch[h+c][c]==0){
q.push(pi(p(h+c,c),cnt+1)); //2 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
ch[h+c][c]=1;
}
if(h-1>=0 && c>=0 && ch[h-1][c]==0 ){
q.push(pi(p(h-1,c),cnt+1)); //3 화면에 있는 이모티콘 중 하나를 삭제한다.
ch[h-1][c]=1;
}
} //while()
}
int main(){
IOFAST();
cin >>n;
bfs();
}
s의 범위가 0~1000까지기 때문에
화면에 있는 이모티콘의 개수는 0~1000까지이다.
1
2
3
4
5
6
7
8
9
10
11
12
if(h<=1000 && h>=0 &&cnt[h][h]==0){
q.push(p(h,h)); //1 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
cnt[h][h]=cnt[h][c]+1;
}
if(h+c<=1000 && h+c>=0 && c>=0 && cnt[h+c][c]==0){
q.push(p(h+c,c)); //2 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
cnt[h+c][c]=cnt[h][c]+1;
}
if(h-1>=0 && c>=0 && cnt[h-1][c]==0 ){
q.push(p(h-1,c)); //3 화면에 있는 이모티콘 중 하나를 삭제한다.
cnt[h-1][c]=cnt[h][c]+1;
}
로 바꿔주니까 많이 줄었다.! !
