아이디어
입력된 숫자부터 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 |
해결방법 :
문제 지문이 짧고 난이도가 d3라 쉬울 것같았지만 쉽게 풀리지 않았던 문제였다.
아름답게 풀기위해 어떤 규칙성과 어떤 로직으로 짤지 고민을 하다가 시간이 많이 지체되서 그냥 무식하게 풀자는 생각을 했다 ㅋㅋ;
나의 아이디어는 다음과같다.
1. 1차원 배열 table에 소수를 미리 체킹해둔다.
2. n = a+b+c 이므로 a,b를 2중 for문 돌리면서 각 숫자가 소수인지 아닌지를 미리 기록해둔 table을 보면서 확인했다. (c는 a,b 정해지면 자동적으로 구하니 for문 안돌림)
3. 여기서 중복된 경우는 제외해줘야 하므로 visit 2차원배열을 만들어서 a,b,c의 중복된 경우를 제외해주었다. (testcase 결과값보면 중복된걸 제외해주었음)
소스코드)
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<stdio.h> #include<cstring> #define MAX 999 int table[1000]; // 소수확인정보 int visit[1001][1001]; int main() { int test_case; int tmp; table[MAX] = 1; // 1은 소수 아닌것 for (int i = 2; i <= 499; i++) { tmp = 2; while (i*tmp <= MAX) { table[i*tmp] = 1; tmp++; } } // 소수체킹 완료 scanf("%d", &test_case); for (int t = 1; t <= test_case; t++) { int ret = 0; int N; scanf("%d", &N); for (int a = 2; a <= N - 4; a++) { for (int b = 2; b <= N - a - 2; b++) { int c = N - a - b; if (!table[a] && !table[b] && !table[c] && !visit[a][b] && !visit[a][c]) { ret++; visit[a][b] = visit[b][a] = 1; visit[a][c] = visit[c][a] = 1; } } } memset(visit, 0, sizeof(visit)); printf("#%d %d\n",t, ret); } } | cs |
| D1 1545번 거꾸로 출력해 보아요 (0) | 2022.05.06 |
|---|---|
| 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=AV5P1kNKAl8DFAUq
문제는 각줄마다 문장이 입력이 되는데 그 문장에서 반복마디를 구하면된다.
-입력-
KOREAKOREAKOREAKOREAKOREAKOREA
SAMSUNGSAMSUNGSAMSUNGSAMSUNGSA
GALAXYGALAXYGALAXYGALAXYGALAXY
EXOEXOEXOEXOEXOEXOEXOEXOEXOEXO
B1A4B1A4B1A4B1A4B1A4B1A4B1A4B1
APINKAPINKAPINKAPINKAPINKAPINK
BLACKPINKBLACKPINKBLACKPINKBLA
TWICETWICETWICETWICETWICETWICE
REDVELVETREDVELVETREDVELVETRED
ABCABCABCABCABCABCABCABCABCABC
-출력-
#1 5
#2 7
#3 6
#4 3
#5 4
#6 5
#7 9
#8 5
#9 9
#10 3
이문제 핵심은 반복마디가 최소로 반복되는 길이여야 한다. 맨마지막 입력예시를 보면 abcabcabcabc라서 abc가 반복이될수도있고
abcabc가 될수도있고 abcabcabc가 반복될수도 있기에 모두 정답이 될 수 있다. 하지만 출력을 보면 이 반복되는 것들 중에서도 최소의 길이를 갖는
반복패턴을 원한 것을 알 수 있었다.
반복마디의 길이가 최대 10길이여서
1~10까지의 반복마디를 각각 생성하고나자마자 만들어진 반복마디와 기존배열을 반복마디의 개수만큼 계속해서 비교해나가주었다.
그렇게되면 하나라도어긋나면 정답이 아니게되므로 자연스럽게 반대의 경우만이 정답이 된다.
소스코드)
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 | #include<iostream> using namespace std; int main() { int test_case; cin >> test_case; for(int t= 1; t<=test_case; t++) { char str[31]; char repeat[11]; //반복 문자열 int cnt; int j; int ret; int k; cin >> str; int len; // 반복 길이 for(len = 1; len <= 10; len++) { cnt = 0; k = 0; for(int i = 0; i<len; i++) { repeat[i] = str[i]; } for( j = len; j<30; j++) { if(cnt == len) { cnt = 0; k = 0; } if(repeat[k++]!= str[j]) { break; } cnt++; } if(j == 30) { ret = len; break; } } cout <<"#"<<t <<' '<< ret << '\n'; } } | cs |
| D1 1545번 거꾸로 출력해 보아요 (0) | 2022.05.06 |
|---|---|
| 5986번 새샘이와 세 소수 (0) | 2018.11.03 |
| 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 |
(로그인 해야볼수있듬!)
해결방법 )
하나의 개구리는 한번의 울음소리 뿐만아니라 여러번 운다는 것이 문제의 힌트같다.
내가 선택한 방법은 전체울음소리와 check할 "croak"을 순차적으로 검사를 하고 원래 녹음된 울음소리에서 기본울음소리 패턴을 제거해 주는 방식을 하면서 답을 구했다. 한번 루프를 돌때마다 cnt를 증가해서 개구리 수를 구했다. (일단 연속되게 운 개구리 한마리를 먼저 걸러내주기 위해서!)
ex)
1)
기본울음소리위치 값과 녹음된 울음소리의 위치 값이 똑같다면 녹음된 울음소리에서 그 값을 빼준다.
그리고 pos 위치를 다음 검사 위치로 이동함!
2)
여기서 눈여겨 봐야할 곳은 녹음된 울음소리의 위치이다.
녹음된 울음소리는 Vector에 저장시키기 때문에 erase(a+i) 를 써서 i번째위치를 삭제시키고 그래서 자동으로 앞으로 당겨지게되어 size가 하나 줄어든다.
그리고 pos 현재위치값과 녹음된 울음소리 위치값이 다르기 때문에 반복인덱스를 하나 증가시킨다.
3)
기본울음소리위치 값과 녹음된 울음소리의 위치값이 똑같기 때문에 제거해주고 뒤에도 남은 위치값이 같으므로 전부 빼지게 된다.
이렇게 되면 녹음된 울음소리에는 “C”만 남게된다.
검사위치가 4까지가서 전부 탐색이 된것이고 5가되면 0으로 다시 만들어줘서 CROAK을 전부 제거했다라는 의미를 부여함
-> pos 위취가 0이면 재탐색 가능!
4)
C는 Pos 처음 값과 같기 때문에 빼준다.
최종적으로 녹음된 울음소리는 없기 때문에 전부 검사를 하게 된 것! 이고, 밑에 기본울음소리에서 검사위치가 0이 아니기때문에 완전한 CROAK을 못만들었다는 의미라서 -1을 출력한다. 만약 0이면 CROAK을 전부 제거했다라는 의미라서 다음 루프타는 것이 가능함
[예외의 경우]
처음부터 검사위치 값과 맞지 않아서, 예외의 경우가 발생하는데
(우리는 한루프를 돌고나서 POS위치가 0이면 CROAK을 전부제거됬다고 정의했기때문) 이는 flag 변수를 설정해서 한번이라도 같은 것이 없는것도 -1이 되게 설정해준다.
코드)
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 | #include<iostream> #include<vector> #include<string> using namespace std; char check[6] = "croak"; vector <char> v; int main() { int test_case; cin >> test_case; for(int t= 1; t<=test_case; t++) { bool flag = false; bool visit = false; int cnt = 0; int vsize = 0; int k = 0; int pos = 0; string str; cin >> str; int len = str.length(); for (int i = 0; i < len; i++) { v.push_back(str[i]); } while (!v.empty()) { vsize = v.size(); k = 0; // 만약 check와 같은 문자가 있으면 k 값으로 사이즈를 줄여주기위해서 필요함 pos = 0; flag = false; visit = false; for (int i = 0; i < vsize - k; i++) { if (v[i] == check[pos]) { v.erase(v.begin() + i); k++; //size 하나 줄임 i--; // i제자리 만들기위해 하나 빼줌 pos++; // pos는 다음 뺄것을 준비하기위해 그위치로 이동 if (pos == 5) { pos = 0;// 다뺏으면 0으로 돌린후 다음 울음소리를 빼기위해 쎗팅! } visit = true; // 이 문자는 있다. } } //한루프가 끝나면 pos 위치 확인 if (pos != 0 || visit == false) { flag = true; break; } cnt++; } if (flag) { printf("#%d -1\n", t); v.clear(); } else printf("#%d %d\n", t, cnt); } } | cs |
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
|---|---|
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |
| SWEA - 혜리의 숫자 나누기 (0) | 2018.09.23 |
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 |
처음에 완전 탐색을 하면서 막대기가 생겨나는 경우의 수(있고 없고)마다 생겨나는 숫자를 M으로 나눠 지는지를 확인했다.
하지만 계속 틀리면서 다시 문제를보니 30만 자리라는 어마어마한 숫자 크기때문에 이렇게 풀면은 안되는 구나를 느꼇다.
결국 질문을 해서 힌트를 얻은결과 숫자 나누는 방법을 적용해서 풀면은 해결할 수 있다고 생각했다.
(나누기는 초딩때부터 아는건데...... 아주 세세하게 들어가서 나머지가 구해지는 과정을 그려보니 알 수 있었다.)
막대기 마다 생겨나는 부분이 M배수가 되는지 확인하면서(%M == 0) 막대기를 배치 시킬 수 있는 경우의 수를 구한다.
위에서 보면 막대기가 가능한 부분은 파란 부분인데, 여기서 생겨나는 왼쪽부분과 오른쪽부분이 M으로 나눠지는지 확인하면서 나눠지면 막대기가 존재할수 있는 수를 카운팅 해준다.
모든 개수를 세주고나서 최종적으로 구한 경우의 수에 -1을 해주면서 CASE 6의 막대기 생겨나는 경우의 수를 없애준다. 왜냐하면 이미 CASE1~5까지 CASE6에 해당하는 부분을 포함하기때문에 -1을 해주는 것이다. 즉, 2^구한 막대기 경우의수-1 을 하면 정답이 되게된다.
막대기때문에 생겨나는 숫자가 M으로 나눠지는지 확인하는 방법은 다음과 같다.
EX) 123456이 7로 나눠지는지 확인 하는 과정 - 우리는 보라색 부분의 식을 반복하면서 최종적으로 0인지 확인하면 된다.
소스코드)
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 | #include<cstdio> #include<iostream> using namespace std; int a[300000];//30만개 숫자 int N; int M; void solve(int t) { int before = 0; int mod = 0; int ret = 1; int cnt = 0; bool flag = false; for (int i = 0; i < N; i++) { mod = (10 * before) + a[i]; // 다음 숫자 생성 mod = mod % M; //숫자를 나눠본다. if (mod == 0) // 나눠지면 막대기 개수 증가 { cnt++; if (i == N - 1) flag = true; } before = mod; // 숫자 생성위해서 현재 나눈 나머지 값을 before로 넘겨준다. } if (!flag) { printf("#%d 0\n", t); return; } else { cnt--; for (int i = 0; i < cnt; i++) { ret = (ret * 2) % 1000000007; } printf("#%d %d\n", t, ret); } } int main() { int T; scanf("%d\n", &T); for (int i = 1; i <= T; i++) { scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) { scanf("%1d", &a[i]); } solve(i); } return 0; } | cs |
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
|---|---|
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |
