아이디어
입력된 숫자부터 0 까지 숫자만 출력해주면 됨. 이때 입력된 숫자는 0보다는 큼.
range(초기숫자(default:0), 끝숫자, 증감수(default:1)) <- 이 파이썬 문법을 이용해서 간단하게 거꾸로 출력
소스 코드
1 2 3 | n = int(input()) for i in range(n,-1,-1) : #n부터 0까지 1씩 감소하면서 i를 생성함. print(i, end= " ") | cs |
| 5986번 새샘이와 세 소수 (0) | 2018.11.03 |
|---|---|
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE
(로그인 해야볼수있듬!)
해결 방법 :
쉬운난이도 문제라고해서 풀어보았는데, 하도 안풀려서 다른 사람의 힌트를 얻고 겨우 풀어낸 문제....
이 문제의 핵심은 최대이득을 구하기위해서는 사고팔고를 적절히 해야하는 방법을 생각해야하는데
그 방법이 맨뒤에서 부터 처음까지 도는 가운데 최대가격의 값을 기준으로 이득이 생기는 부분의 총합을 더하는 것이었다.
내가 헤맨것이 모든 가격을 내림차순으로 최대값순으로 새로운 배열을 만들고 만든 배열과 주어진 가격 배열을 하나씩 비교해 나가면서 더해나간게 문제였다.
예시의 테스트케이스는 다 통과되서 아 이게 맞다라고 생각하고(답정) 한게 큰 패인이다..
1 1 4 5 2 1 이 테스트케이스만 보더라도 5 4 2 1 1 1 이런 새로운 배열과 하나씩 비교할텐데, 4가 5안에 포함되어버려 이미 계산이 끝낫지만 여전히 새로운 배열에 비교 대상으로 존재해있어서 뒤에 2, 1 부분도 계산을 해준것이기 때문이다 ...
엄청난 뻘짓을 하고나서 힌트를 본후 , 대부분 사람들은 뒤에서 부터 계산을 해서 답을 찾았다는 것을 보았고,
아 그럼 뒤에서 부터 최대값을 갱신해주고 그 최대값보다 작으면 계속더해가는 방식이 모든 경우를 해결해 줄 수 있다는 것을 알게되었다.
위의 1 1 4 5 2 1 을 보면
맨뒤의 1을 max로 둔다.
그리고 맨뒤에서부터 처음일때까지 전부 비교해준다.
만약 현재 max 보다 크다면 max만 갱신해준다.
아니라면 max값보다 작으므로 이득을 더해나가준다.
이렇게 전부 계산해주고나면, 이득생기는 부분을 전부더해줘서 최대이득을 구할 수 있게된다.
소스코드)
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 | #include<iostream> long long max_margin = 0; int cost[1000001]; using namespace std; int main() { int test_case; cin >> test_case; for (int t = 1; t <= test_case; t++) { max_margin = 0; int max_price; int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &cost[i]); } max_price = cost[n - 1]; for (int i = n - 2; i >= 0; i--) { if (max_price > cost[i]) { max_margin += max_price - cost[i]; } else { max_price = cost[i]; } } printf("#%d %lld\n", t, max_margin); } } | cs |
| 5986번 새샘이와 세 소수 (0) | 2018.11.03 |
|---|---|
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |
1 2 3 4 5 6 7 8 9…
입력10
출력1 2 - 4 5 - 7 8 - 10
3, 6, 9 가 들어가있으면 박수대신 "-" 표시를 출력한다. 이때, 333 이라는 숫자가 들어오면 --- 으로 출력된다.
해결방법)
n이 입력되면
1부터 n까지 주어지는 상황에서
각 숫자 자리마다 3,6,9가 있는지 확인한 후 있으면 있는만큼 "-"출력한다. 없으면 원래 숫자를 출력한다.
여기서 각 숫자마다 자리를 나눠서 확인을 해줘야하는데 10으로 계속 나눠주면서 몫이 0일때 까지 반복한다.
그래서 반복마다 생겨나는 나머지가 각 자리수이기 때문에 이 자리수가 3,6,9인지를 확인해 주었다.
예시) 245 / 10 = 24, 245 % 10 = 5(일의자리수 추출) -> 24/10 = 2, 24%10 = 4(십의자리수 추출) -> 2/10= 0, 2%10 = 2(백의자리수 추출)
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 | #include<iostream> using namespace std; int main() { int n; int num; int mok; int obj; // 나누는 대상 int r; // 나머지값 bool flag = 0; //1로 켜지면 3,6,9가 하나라도 있었다라는것 cin >> n; for(int num = 1; num<=n; num++) { obj = num; flag = 0; do { r = obj % 10; if(r == 3 || r == 6 || r == 9) { flag = 1; printf("-"); } mok = obj/10; obj = mok; }while(mok!=0); if(flag == 1) { printf(" "); continue; } printf("%d ",num); } } | cs |
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
|---|---|
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |
| SWEA - 혜리의 숫자 나누기 (0) | 2018.09.23 |
풀이방법)
나는 먼저 0인 좌표(주변의 지뢰가 없는곳)를 찾아 탐색을 해서 먼저 방문영역을 체크해두기로했다.
- 여기서 탐색을 한다는 것은 한번의클릭으로 모두 제거되는 것이기 때문에 카운트를 하나로 취급해준다.
그리고 모든 좌표를 탐색하면서 방문이 안된 녀석들은 주변에 지뢰가 있는 것이기때문에 하나씩 카운트를 세준다.
1. 모든좌표마다 8방향 주변에 지뢰개수를 파악해서 그 개수를 표시해주는 맵을 새로 만든다.
2. 새로운 맵에서 0인 좌표부터 bfs 탐색을 시작해서 주변의 영역을 방문표시해둔다.
3. 인접한 0들은 모두 2번에서 없어진 것이고, 나머지 방문안된 0도 bfs탐색을 하면서 주변영역을 방문표시해준다.
4. bfs탐색을 한번할때마다 카운트를 1씩증가한다.
5. 최종적으로 원래 맵을 돌면서 방문안된 좌표는 하나씩 카운트를 세주고 3번에서 구한 카운트와 합산하면 정답이다.
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include<iostream> #include<queue> #include<cstring> using namespace std; int changemap[301][301] = { 1, }; char basemap[301][301]; int visit[301][301]; int n; int dx[] = { -1,-1,-1,0,1,1,1,0 }; int dy[] = { -1, 0, 1, 1,1,0,-1,-1 }; queue< pair<int, int> > q; bool isInmap(int x, int y) { if (x <0 || x >n - 1 || y<0 || y>n - 1) { return false; } else return true; } void Change() { for (int x = 0; x<n; x++) { for (int y = 0; y<n; y++) { //각 좌표마다 8방향에서 지뢰개수를 채워나간다. int cnt = 0; if (basemap[x][y] == '*') { changemap[x][y] = -1; continue; } for (int i = 0; i<8; i++) { int tx = x + dx[i]; int ty = y + dy[i]; if (basemap[tx][ty] == '*') { cnt++; } } changemap[x][y] = cnt; } } } void bfs(int x, int y) { // bfs탐색으로 0인 좌표에서 8방향 값을 visit 체크해준다. int nx, ny, nnx, nny; q.push({ x,y }); while (!q.empty()) { nx = q.front().first; ny = q.front().second; visit[nx][ny] = 1; for (int i = 0; i<8; i++) { nnx = nx + dx[i]; nny = ny + dy[i]; if (!isInmap(nnx, nny)) { continue; } if (!visit[nnx][nny]) { visit[nnx][nny] = 1; // 방문안된 좌표는 방문처리해준다. 중복 방문표시 예방 if (changemap[nnx][nny] == 0) { q.push({ nnx,nny }); } } } q.pop(); } } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { int ret = 0; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf(" %c", &basemap[i][j]); } } Change(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (changemap[i][j] == 0 && !visit[i][j]) { bfs(i, j); ret++; // bfs탐색한다면 클릭횟수증가. } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (changemap[i][j] > 0 && !visit[i][j]) { ret++; } } } printf("#%d %d\n", t, ret); memset(visit, 0, sizeof(visit)); } } | cs |
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
|---|---|
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| SWEA - 혜리의 숫자 나누기 (0) | 2018.09.23 |